CODEWITHSUNDEEP
haskell
Paul Stelian
Paul Stelian

Reputation: 1379

How can I convert a Cons list to a Haskell list without (explicit) recursion?

I have the following type: data ConsList elem = Nil | Cons elem (ConsList elem)

How can I convert a list of this form into a Haskell list, with the conversion not being recursive?

That is, I want (Cons 3 (Cons 5 (Cons 7 Nil))) to convert to [3,5,7], or to (3:(5:(7:[]))) if you wish, and that without actually using a recursive function.

I don't think using fold is okay since this type doesn't actually have it overloaded and I don't see how I could overload fold without actually having explicit recursion.

Upvotes: 2

Views: 598

Answers (1)

Paul Stelian
Paul Stelian

Reputation: 1379

I found the solution for simple data structures is to simply derive Foldable. Apparently though it didn't seem to work even for this structure, let alone the more complicated one I actually needed.

There is a function unfoldr. Its type signature is:

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

Essentially it takes a function which produces the next element of the list and the remainder.

We would call it like:

unfoldr unwrapElem l

and unwrapElem itself is defined such as:

unwrapElem :: (ConsList e) -> Maybe (e, ConsList e)
unwrapElem Nil = Nothing
unwrapElem (Cons el rem) = Just (el,rem)

One thing to notice is that there still is recursion, however it is implicit now (within unfoldr itself)

Upvotes: 3

Related Questions