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.]
Hi!
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
improvement:
unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
unfoldr u x = build (g x)
where
g x c n = f x
where
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
where
u x | p x = Nothing
| otherwise = Just (h x, t x)
===
Greetings,
Carsten
--
Carsten Schultz (2:38, 33:47), FB Mathematik, FU Berlin
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
More information about the Glasgow-haskell-users
mailing list