Re: [Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
Lennart Augustsson wrote: Sure, but we also have para f e xs = snd $ foldr (\ x ~(xs, y) -> (x:xs, f x xs y)) ([], e) xs Nice one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
Sure, but we also have para f e xs = snd $ foldr (\ x ~(xs, y) -> (x:xs, f x xs y)) ([], e) xs So I think using para is fine. -- Lennart On Feb 12, 2007, at 18:40 , Bernie Pope wrote: Nicolas Frisby wrote: Guess this is a tricky choice for a foldr intro, since it requires a "paramorphism" (see bananas lenses wires etc.) para :: (a -> [a] -> b -> b) -> b -> [a] -> b para f e [] = e para f e (x:xs) = f x xs (para f e xs) -- note that the original tail of the list (i.e. xs and not xs') is used in the else-branch dropWhile' p = para (\x xs xs' -> if p x then xs' else (x:xs)) [] Actually, several people tried to use para, but of course it is not in the spirit of the challenge :) Cheers, Bernie. ___ 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] Foldr tutorial, Inspired by Getting a Fix from a Fold
Oops; I totally forgot the context of this whole discussion! I enjoyed your article. On 2/12/07, Bernie Pope <[EMAIL PROTECTED]> wrote: Nicolas Frisby wrote: > Guess this is a tricky choice for a foldr intro, since it requires a > "paramorphism" (see bananas lenses wires etc.) > > para :: (a -> [a] -> b -> b) -> b -> [a] -> b > para f e [] = e > para f e (x:xs) = f x xs (para f e xs) > > -- note that the original tail of the list (i.e. xs and not xs') is > used in the else-branch > dropWhile' p = para (\x xs xs' -> if p x then xs' else (x:xs)) [] Actually, several people tried to use para, but of course it is not in the spirit of the challenge :) Cheers, Bernie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
Nicolas Frisby wrote: Guess this is a tricky choice for a foldr intro, since it requires a "paramorphism" (see bananas lenses wires etc.) para :: (a -> [a] -> b -> b) -> b -> [a] -> b para f e [] = e para f e (x:xs) = f x xs (para f e xs) -- note that the original tail of the list (i.e. xs and not xs') is used in the else-branch dropWhile' p = para (\x xs xs' -> if p x then xs' else (x:xs)) [] Actually, several people tried to use para, but of course it is not in the spirit of the challenge :) Cheers, Bernie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
Guess this is a tricky choice for a foldr intro, since it requires a "paramorphism" (see bananas lenses wires etc.) para :: (a -> [a] -> b -> b) -> b -> [a] -> b para f e [] = e para f e (x:xs) = f x xs (para f e xs) -- note that the original tail of the list (i.e. xs and not xs') is used in the else-branch dropWhile' p = para (\x xs xs' -> if p x then xs' else (x:xs)) [] Prelude> dropWhile' (<5) [1,2,3,4,5,6,7,8] [5,6,7,8] Prelude> dropWhile' (<5) [1,2,3,4,5,6,7,1] [5,6,7,1] Prelude> :m + Test.QuickCheck Prelude Test.QuickCheck> :m + Text.Show.Functions Prelude Test.QuickCheck Text.Show.Functions> quickCheck $ \p l -> dropWhile p (l :: [Int]) == dropWhile' p l Loading package QuickCheck-1.0 ... linking ... done. OK, passed 100 tests. On 2/12/07, Donald Bruce Stewart <[EMAIL PROTECTED]> wrote: pixel: > Chris Moline <[EMAIL PROTECTED]> writes: > > > dropWhile p = foldr (\x l' -> if p x then l' else x:l') [] > > invalid: dropWhile (< 5) [1, 10, 1] should return [10, 1] Prelude Test.QuickCheck Text.Show.Functions> quickCheck $ \p xs -> dropWhile p xs == foldr (\x l' -> if p x then l' else x:l') [] (xs :: [Int]) Falsifiable, after 4 tests: [-1,-3,1] If in doubt, do a quick check! -- Don ___ 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] Foldr tutorial, Inspired by Getting a Fix from a Fold
pixel: > Chris Moline <[EMAIL PROTECTED]> writes: > > > dropWhile p = foldr (\x l' -> if p x then l' else x:l') [] > > invalid: dropWhile (< 5) [1, 10, 1] should return [10, 1] Prelude Test.QuickCheck Text.Show.Functions> quickCheck $ \p xs -> dropWhile p xs == foldr (\x l' -> if p x then l' else x:l') [] (xs :: [Int]) Falsifiable, after 4 tests: [-1,-3,1] If in doubt, do a quick check! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
Chris Moline <[EMAIL PROTECTED]> writes: > dropWhile p = foldr (\x l' -> if p x then l' else x:l') [] invalid: dropWhile (< 5) [1, 10, 1] should return [10, 1] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
I hope the following doesn't come across as condescending... The recent issue of The Monad Reader has generated some excitement, mostly to do with the time travel article. I, however, would like to discuss a simpler solution to implementing dropWhile with foldr, which is discussed in the first article of TMR. When I was taught about folds, I was told that foldr starts at the end of the list and then builds up the result from there. But this turns out to be an unhelpful way of thinking. It's better to say foldr starts at the beginning of the list, just like foldl. But how does this work? To see, we'll start by implementing a simpler function than dropWhile, one which determines whether we should cons an element onto a list or just return the list. dropHead p x xs = if p x then xs else x:xs Note that I've funnily given a separate arg to the head of the list and to its tail. That's not a typo and later we will see why. Now let's apply dropHead to each element of the list [1, 2, 3, 4, 5]: map (dropHead p) [1, 2, 3, 4 ,5] => [dropHead p 1, dropHead p 2, dropHead p 3, dropHead p 4, dropHead p 5] Now we need to figure out where to get the second argument for each of the dropHead applications. I know! If a call to dropHead comes before another call to dropHead, we'll pass the result of the second call as the second arg of the first. And if there are no calls after a call to dropHead, we'll pass our base case as the second arg to that call. Let's have a look: threadResults basec [] = basec threadResults basec [f:fs] = f $ threadResults basec fs threadResults [] [dropHead p 1 ...] = dropHead p 1 $ dropHead p 2 $ dropHead p 3 $ dropHead p 4 $ dropHead p 5 [] Let's see it in action! First let's let our predicate determine whether a value is less than three. dropHead (< 3) 5 [] = if (< 3) 5 then [] else 5:[] => [5] dropHead (< 3) 4 [5] = if (< 3) 4 then [5] else 4:[5] => [4, 5] dropHead (< 3) 3 [4, 5] = if (< 3) 3 then [4, 5] else 3:[4, 5] => [3, 4, 5] dropHead (< 3) 2 [3, 4, 5] = if (< 3) 2 then [3, 4, 5] else 2:[3, 4, 5] => [3, 4, 5] dropHead (< 3) 1 [3, 4, 5] = if (< 3) 1 then [3, 4, 5] else 1:[3, 4, 5] => [3, 4, 5] => [3, 4, 5] Do you now see how foldr works? It starts at the beginning of the list and applies the function you gave it to the first element of the list. Then to get the second argument of the first call, it applies your function to the second element of the list and passes the result of that to the first call. In other words, it /recurs/ on the next element of the list. When we finally get to the end, the base case is passed to the final call of your function and it returns, and all the previous calls return building their results from the calls after. So in other words to implement dropWhile with foldr merely requires: dropHead p x xs = if p x then xs else x:xs dropWhile p l = foldr (dropHead p) [] l Or even simpler: dropWhile p = foldr (\x l' -> if p x then l' else x:l') [] take 3 $ dropWhile (< 5) [1..] => [5, 6, 7] No abtruse machinery required! __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
