Building a list from a non-traversable without recursion

Question

I can build a data structure that is a member of the Traversable typeclass (e.g. List or Map), by mapping (map, mapM) or folding (foldl, foldM) another traversable data structure.

However, I often encounter situations where I need to build a traversable data structure with a member of the Num typeclass (e.g. Integer).

My usual approach here is to build a list by using a recursive operation - for example:

foo :: Integer -> [Integer] -> [Integer]
foo n fs
  | m < 2 = fs
  | rem m 2 == 0 = foo (m - 1) (m:fs)
  | otherwise = foo (m - 1) fs
  where m = abs n

This function returns the absolute values of the integers that are divisible by two, and are between 2 and n (inclusive).

Using the above example, is there an idiomatic way to build a list from a non-traversable without using recursion?

Answer 1

You're asking for a way to build a list from a non-traversable object without using recursion, but I don't think this is really what you want. After all, any traversal is going to use recursion — how do you think map and foldl are implemented? I think the more precise question you're asking is whether there's a well-known function or built-in way to express a so-called "numeric fold" where the recursion is "behind the scenes", or implicit, instead of explicit as in your foo example.

Well, one simple way to achieve this is to write a foldNum function yourself. For instance:

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

Then, you can define foo as:

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

---

If you're a little disappointed with this, I understand why: you haven't really saved much by using this definition of foldNum. In fact, the definition I give above doesn't even have a built-in base case. The problem with folding a number is that there are lots of ways to do it! You can subtract or add any amount on each step, and there's no clear place to stop (zero might seem a natural place to stop, but that's only true for non-negative numbers). One way to proceed is to try to make our foldNum even more generic. How about:

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)

Now, we can write foo as:

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

Maybe this is what you're looking for?

---

Footnote: Just as lists can be folded left or right (foldl and foldr), soo too can we fold numbers in two different ways. You can see this by replacing the last line of the above foldNum definition with::

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

For instance, for foo the difference between these two is the order of the resulting list.

Answer 2

Since you're going from 2 to n, and filtering out values, use the filter function designed just for this:

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

Answer 3

I think what you might be looking for is the library function unfoldr from Data.List. It has signature:

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

It generates a list [a] from a value of type b which can be non-traversable. It operates by repeatedly applying its first argument to the b value to get a fresh a value to add to the list and an updated b value for the next call, until it gets Nothing which ends the list.

Note that it doesn't allow you to skip certain bs without generating any as or let you generate multiple as for a single b. However, you can work around that limitation by returning a list of lists and then concatenating. So, your foo example would look like:

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

In many more realistic scenarios, you don't need to concat lists of lists. For example:

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]]