Building a list from a non-traversable without recursion

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?

Solution

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.