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?
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.
Matthias Görgens
Thanks to Jason and Felipe. I'll try that approach.
http://www.nabble.com/There%27s-nothing-wrong-with-infinite-types!-td7713737... Which explains the problem. -- aycan
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 -> []
On Jul 22, 7:44 pm, Felipe Lessa
type TypeOfF a = a -> Maybe (TypeOfF' a) newtype TypeOfF' a = F {unF :: TypeOfF a}
An interesting observation is that "ListT ((->) a) ()" would also do the job. If one would want to also generalize "filter" this way, a more appropriate type would be "ListT ((->) a) Bool", which could still be used for the generalized takeWhile, dropWhile, etc. You need to import Control.Monad.Reader for the Monad instance of "(-
) a". ListT here isn't the one from mtl, but rather the one from "http:// www.haskell.org/haskellwiki/ListT_done_right" or from the "generator" package in hackage.
2009/7/22 Matthias Görgens
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?
At a quick glance it looks to me like the type of f is infinite. Something like: f :: a -> Maybe (a -> Maybe (a -> ...)) When I've seen people solve similar problems in the past they have introduced a data type to hide the infinite type. See for example, the solution to defining fix: http://blog.plover.com/prog/springschool95-2.html I didn't actual read that article, but it appears to explain the technique. Jason
What is the use case(s) for this function? lements 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? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Thu, Jul 23, 2009 at 07:28:55AM +0200, Matthias Görgens wrote: ] I often want to take one more element than takeWhile does, or only
takeWhileMore n p x | p x = Just . F $ takeWhileMore n p | otherwise = Just . F $ takeN n
] start checking the predicate after taking the first element for sure.
plusFirst = const . Just . F
] Or both.
both = plusFirst . takeWhileMore 1
:) -- Felipe.
participants (7)
-
Anton van Straaten -
Aycan iRiCAN -
Felipe Lessa -
Jason Dagit -
Matthias Görgens -
Thomas Hartman -
yairchu＠gmail.com