unfold deforestation

Carsten Schultz carsten at codimi.de
Thu Sep 2 09:37:21 EDT 2004

[If this should have gone to a different list, please tell me and I
 will subscribe to that.]


There is no rule in standard libs related to unfoldr.  From short
googling I know that there may be several approaches to this, but as
long as nothing fancy is introduced, the following might be a simple

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

unfoldr u x = build (g x)
    g x c n = f x
	f x = case u x of
		       Just (h,t) -> h `c` f t
		       Nothing -> n

{-# INLINE unfoldr #-}

It makes unfoldr a good producer and works nicely with the following
example from `The Under-Appreciated Unfold' (Gibbons&Jones):

module Tree(Tree(..), bftf) where

import Unfold

data Tree a = Nd a [Tree a]

root (Nd r _) = r

kids (Nd _ ks) = ks

bftf = concat . levelf

levelf = unfold null (map root) (concat . map kids)

unfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]

unfold p h t = unfoldr u 
    u x | p x       = Nothing
	| otherwise = Just (h x, t x)



Carsten Schultz (2:38, 33:47), FB Mathematik, FU Berlin
PGP/GPG key on the pgp.net key servers, 
fingerprint on my home page.

More information about the Glasgow-haskell-users mailing list