[Haskell-cafe] Generalizing takeWhile
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? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
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.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
2009/7/22 Matthias Görgens matthias.goerg...@googlemail.com 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
Thanks to Jason and Felipe. I'll try that approach. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
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 - []
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
Matthias Görgens matthias.goerg...@googlemail.com writes: Thanks to Jason and Felipe. I'll try that approach. http://www.nabble.com/There%27s-nothing-wrong-with-infinite-types!-td7713737.html Which explains the problem. -- aycan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
What is the use case(s) for this function? I often want to take one more element than takeWhile does, or only start checking the predicate after taking the first element for sure. Or both. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
