[Haskell-cafe] Generalizing takeWhile

[Anton van Straaten]

Felipe Lessa wrote:
> On Wed, Jul 22, 2009 at 06:00:38PM +0200, Matthias Görgens wrote:
> ] I need to take some elements from the front of a list.  However the
> ] criteria are somewhat complex.
> ]
> ] > walk f [] = []
> ] > walk f (x:xs) = case f x
> ] >                 of Just g -> x : walk g xs
> ] >                    Nothing -> []
> ]
> ] For each item the `predicate' f either returns Nothing, when it thinks
> ] we should not take any more elements, or return Just another
> ] `predicate' to apply to the next element.
> ]
> ] However the type system does not like my function.  How can I mollify it?
> 
> It's actually simple!  The problem is the type of 'f' would be
> 
>   type TypeOfF a = a -> Maybe (TypeOfF a)
> 
> However, this type synonym isn't valid for the obvious reason (it
> is "infinite", I don't remember the correct name).  Data types,
> on the other hand, may be recursive.
> 
>> type TypeOfF a = a -> Maybe (TypeOfF' a)
>> newtype TypeOfF' a = F {unF :: TypeOfF a}

Another way to do it is to use an alternative to Maybe, defined like this:

 > data MaybeFun a = NoFun | Fun (a -> MaybeFun a)

...which gives this definition for walk:

 > walk :: (a -> MaybeFun a) -> [a] -> [a]
 > walk f [] = []
 > walk f (x:xs) = case f x
 >                 of Fun g -> x : walk g xs
 >                    NoFun -> []