[Haskell-cafe] Hand calculation of Bird's definition of zip using
foldr
Miguel Mitrofanov
miguelimo38 at yandex.ru
Thu Mar 12 13:34:41 EDT 2009
zip [1,2,3] [4,5,6] = zip (1:2:3:[]) (4:5:6:[]) = foldr f e (1:2:3:[])
(4:5:6:[]) = f 1 (foldr f e (2:3:[])) (4:5:6:[]) = (1, 4) : foldr f e
(2:3:[]) (5:6:[]) = (1, 4) : f 2 (foldr f e (3:[])) (5:6:[]) = (1,
4) : (2, 5) : foldr f e (3:[]) (6:[]) = (1, 4) : (2, 5) : f 3 (foldr f
e []) (6:[]) = (1, 4) : (2, 5) : (3, 6) : foldr f e [] [] = (1, 4) :
(2, 5) : (3, 6) : e [] = (1, 4) : (2, 5) : (3, 6) : [] = [(1, 4), (2,
5), (3, 6)]
On 12 Mar 2009, at 20:01, R J wrote:
> Can someone provide a complete hand calculation of zip [1,2,3]
> [4,5,6] using the following definition of zip, based on foldr:
>
> zip :: [a] -> [b] -> [(a, b)]
> zip = foldr f e
> where
> e ys = []
> f x g [ ] = []
> f x g (y : ys) = (x , y) : g ys
>
>
> foldr :: (a -> b -> b) -> b -> ([a] -> b)
> foldr _ e [] = e
> foldr f e (x : xs) = f x (foldr f e xs)
>
>
> This implementation of zip produces the expected result [(1, 4), (2,
> 5), (3, 6)], but I'm unable to do the hand calculation and don't
> understand why it works. Part of my problem is that "e" is defined
> as a function that takes one argument, I don't see how that fits in
> with the usual scheme for foldr, which, as I understand it, is:
>
> foldr f e [x1, x2, ...] = f x1 (f x2 (f x3 ...(f xn e)))...
>
> Thanks, as always, to all in this great community.
>
>
> Windows Live™: Keep your life in sync. Check it
> out._______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
More information about the Haskell-Cafe
mailing list