[Haskell-cafe] Generalizing takeWhile

[Felipe Lessa]

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}

and you may write your function as

> walk :: TypeOfF a -> [a] -> [a]
> walk _ []     = []
> walk f (x:xs) = case f x of
>                   Just g  -> x : walk (unF g) xs
>                   Nothing -> []

Some test predicates

> takeN :: Num a => a -> TypeOfF b
> takeN 0 = const Nothing
> takeN n = const . Just . F . takeN $ n-1

> zigZag :: (a -> Bool) -> TypeOfF a
> zigZag p = go True
>   where go b x | p x == b  = Just . F $ go (not b)
>                | otherwise = Nothing

--
Felipe.