Iterating (mapping) recursive data type in Haskell

Question

This might me a stupid question, but since I don't have anyone to discuss it over a coffee, I think I'd ask it here. So, I'm reading the book "The Haskell School of Expression" to learn myself a bit of Haskell and they have the following type:

data Picture = Region Color Region
         | Picture `Over` Picture
         | EmptyPic
deriving Show

Later, when they need to convert a picture into a list of regions they do it recursively like this:

picToList EmptyPic = []
picToList (Region c r) = [(c, r)]
picToList (p1 'Over' p2) = picToList p1 ++ picToList p2

This is all good and rather easy, but what made me thinking is that they had to do it manually. Haskell is packed with abstractions, so I wonder, does it have an abstraction for iterating over recursive data types? After all, the compiler knows the structure of the data type, and internally it probably represents the data as a graph of some kind, so can it traverse it for me via some generic way? I've no idea how it would work in practice, but still, Haskell is different enough from all the others programming languages I know, so, maybe there is some concept I can't even imagine that does it.

Answer 1

Traversal is not trivial. While it seems that you have a simple tree, it doesn't have to be that way. Do we only iterate over the leafs or do we do pre-order or post-order traversal? If we have a graph rather than a tree, how do we manage duplicate elements? This is best answered by whoever is implementing that data structure, not by the compiler.

Answer 2

Depending on exactly what you want to do there is:

Data.Functor
Data.Foldable
Data.Traversable

Functor allows you to map over your structure, Foldable, obviously allows a fold and Traversable does a map and fold. Now I haven't used it my self but there does appear to be ways to get the compiler to automatically derive instances for these typeclasses for you (I have no idea if this is possible in the case you give however)

A couple of things to note here are:

This introduces both typeclasses and some magic to automatically write them, so could easily be a reason for leaving them out of tutorial in a book if those topics have not been introduced.

Also, of course, most imperative languages you would have to explicitly program a traversal on any new structure any way, so this may not be a feature the reading is expecting to be available.

Answer 3

This doesn't directly answer your question, but there is a typeclass Foldable that includes the function toList :: Foldable t => t a -> [a]. Furthermore, GHC is capable of deriving instances for it, as in the following trivially simple code:

{-# LANGUAGE DeriveFoldable #-}

data Foo a = Foo a (Foo a)
           | Bar
             deriving (Show, Foldable)

Using it in GHCi:

GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> :load derive-foldable.hs
[1 of 1] Compiling Main             ( derive-foldable.hs, interpreted )
Ok, modules loaded: Main.
*Main> import qualified Data.Foldable as F
*Main F> let f = Foo 1 (Foo 2 (Foo 3 Bar))
*Main F> F.toList f
[1,2,3]

This doesn't apply in your case, not least because (in basic, imprecise terms) your Picture type doesn't have a parameter. However, it is indeed an abstraction for iterating over recursive data types. This automatic derivation of a Foldable instance is more GHC magic and less essential Haskell functionality, though.