Построение списка из непроходимого без рекурсии

Вы просите создать список из непроходимого объекта без использования рекурсии, но я не думаю, что это действительно то, что вам нужно. В конце концов, любой обход будет использовать рекурсию — как вы думаете, как реализованы map и foldl? Я думаю, что более точный вопрос, который вы задаете, заключается в том, есть ли известная функция или встроенный способ выразить так называемую числовую складку, где рекурсия находится за кулисами, или неявная, а не явная, как в вашем примере foo .

Что ж, один простой способ добиться этого — написать foldNum функцию самостоятельно. Например:

foldNum :: Num n => (n -> a -> a) -> n -> a
foldNum f n = f n (foldNum f (n - 1))

Затем вы можете определить foo как:

foo :: Integer -> [Integer]
foo = reverse . foldNum go . abs
  where
    go n a | n < 2        = []
           | rem n 2 == 0 = n:a
           | otherwise    = a

Если вы немного разочарованы этим, я понимаю, почему: вы не очень много сэкономили, используя это определение foldNum. На самом деле определение, которое я дал выше, даже не имеет встроенного базового варианта. Проблема сложения числа в том, что есть много способов сделать это! Вы можете вычесть или добавить любую сумму на каждом шаге, и нет четкого места для остановки (ноль может показаться естественным местом для остановки, но это верно только для неотрицательных чисел). Один из способов продолжить работу — попытаться сделать наш foldNum еще более универсальным. Как насчет:

foldNum :: (n -> a -> a) -> (n -> Bool) -> (n -> n) -> a -> n -> a
foldNum f stop step a n
  | stop n = a
  | otherwise = foldNum f stop step (f n a) (step n)

Теперь мы можем записать foo как:

foo :: Integer -> [Integer]
foo = foldNum (\x a -> if even x then x:a else a) (< 2) (subtract 1) [] . abs

Может быть, это то, что вы ищете?

Примечание: точно так же, как списки можно сворачивать влево или вправо (foldl и foldr), мы можем складывать числа двумя разными способами. Вы можете увидеть это, заменив последнюю строку приведенного выше определения foldNum на::

  | otherwise = f n $ foldNum f stop step a (step n)

Например, для foo разница между ними заключается в порядке результирующего списка.

Поскольку вы переходите от 2 к n и отфильтровываете значения, используйте функцию filter, предназначенную именно для этого:

foo :: Integer -> [Integer]
foo n = filter (\x -> x `mod` 2 == 0) [2..n]

Я думаю, что вы, возможно, ищете библиотечную функцию unfoldr из Data.List. Он имеет подпись:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Он генерирует список [a] из значения типа b, которое может быть непроходимым. Он работает, многократно применяя свой первый аргумент к значению b, чтобы получить новое значение a для добавления в список и обновленное значение b для следующего вызова, пока не будет получено Nothing, которое заканчивает список.

Обратите внимание, что он не позволяет вам пропускать определенные b без создания каких-либо a или создавать несколько a для одного b. Однако это ограничение можно обойти, вернув список списков, а затем объединив их. Итак, ваш пример foo будет выглядеть так:

foo = concat . unfoldr step
  where step n | m < 2 = Nothing  -- time to stop
               | rem m 2 == 0 = Just ([m], m-1)  -- return one element
               | otherwise    = Just ([], m-1)   -- return no elements
          where m = abs n

Во многих более реалистичных сценариях вам не нужно concat списки списков. Например:

import Data.List

bar :: Int -> [[Int]]
bar n = unfoldr step 1
  where step k | k > n     = Nothing
               | otherwise = Just (replicate k k, k + 2)

main = do
  print $ bar 10
  -- [[1],[3,3,3],[5,5,5,5,5],[7,7,7,7,7,7,7],[9,9,9,9,9,9,9,9,9]]