Hey guys, I was working through 99 Haskell Problems a while back and while refactoring my solution to Problem 9 I couldn't help feeling I was reinventing something basic. My thinking was, this problem can be generalized to letting a function recursively process arbitrary chunks of a given data structure in several passes until the whole data is consumed while some function is extracting some information in an accumulator. So I wrote a mini-typeclass like so: class Exhaustible e where isEmpty :: e -> Bool instance Exhaustible [a] where isEmpty = null exhaust :: Exhaustible e => (e -> (b, e)) -> (a -> b -> a) -> a -> e -> a exhaust f g z xs | isEmpty xs = z | otherwise = let (val, rest) = f xs in exhaust f g (g z val) rest Now the solution to Problem 9 is easy to define in terms of "exhaust". Then I thought, "Why am I treating empty as a special value again?", and wrote this instead: stabilize :: Eq a => (a -> (b, a)) -> (c -> b -> c) -> c -> a -> (c, a) stabilize f g z d | d == d' = (z', d') | otherwise = stabilize f g z' d' where (val, d') = f d z' = g z val This looks both really useful and extremely basic to me, so I'm wondering what the standard way to do the same thing might be. I looked at Foldable + foldr but the idea there seems to be to process a data structure _one_ element at a time. So my question is, is there an official implementation for this combinator I called "stabilize"? Also, any tips on improving the definitions and comments on how situations like Problem 9 should be approached are welcome. Daniel
On 2014-09-16 23:11, Dániel Arató wrote: Then I thought, "Why am I treating empty as a special value again?",
and wrote this instead:
stabilize :: Eq a => (a -> (b, a)) -> (c -> b -> c) -> c -> a -> (c, a) stabilize f g z d | d == d' = (z', d') | otherwise = stabilize f g z' d' where (val, d') = f d z' = g z val
This looks both really useful and extremely basic to me, so I'm wondering what the standard way to do the same thing might be.
I think you reinvented the 'unfoldr' function here: unfoldr :: (b -> Maybe (a, b)) -> b -> [a] It applies the given function to the second argument until the function returns Nothing, which correponds to your "d == d'" guard. You could use it to solve Problem 9 like pack :: Eq a => [a] -> [[a]] pack = unfoldr (\xs -> if null xs then Nothing else Just (span (== head xs) xs)) I think this looks like it does two things at once:
I looked at Foldable + foldr but the idea there seems to be to process a data structure _one_ element at a time.
It's true that a fold processes a data structure one element at a time, but you also have access to the accumulator, i.e. you can consider what you processed so far. I think you could solve Problem 9 using a foldr like pack :: Eq a => [a] -> [[a]] pack = foldr go [] where go x acc@(a:as) = if x == head a then (x:a):as else [x]:acc go x _ = [[x]] - Frerich
participants (2)
-
Dániel Arató -
Frerich Raabe