[Haskell-cafe] Sequence differences

[Ross Mellgren]

Well, it is mapping, but take a look at the type of zip:

zip :: [a] -> [b] -> [(a,b)]  (that is, two lists in, list of tuples  
out)

so you can use map, which has the type:

map :: (a -> b) -> [a] -> [b]

over a zipped list, e.g.: map f (zip a b)

Because [a] is [(a,b)] (the result of zip), the type of map becomes

((a,b) -> c) -> [(a,b)] -> [c]

Most binary functions such as (-) (subtract) do not take a tuple as an  
argument, they are curried, e.g.

(-) :: Num a => a -> a -> a

So you can use the uncurry function to transform these curried binary  
functions into unary functions that take tuples

uncurry :: (a -> b -> c) -> (a,b) -> c

so,

uncurry (-) :: Num a => (a,a) -> a

which you can use as the first argument to map

map (uncurry (-)) :: Num a => [(a,a)] -> [a]

and then pipe in the zip

map (uncurry (-)) (zip as bs) :: [a]

in your case, you want 'as' to be the second and subsequent elements  
of the list, tail, and 'bs' to be the first and subsequent elements of  
the list, so

l :: [Int]
l = [0,1,3,6,10,15,21,28]
map (uncurry (-)) (zip (tail l) l)

which you can generalize and wrap up in a function:

s :: (a -> a -> b) -> [a] -> [b]
s f l = map (uncurry f) (zip (tail l) l)

there's also the list comprehension version, where you move the  
'uncurry' behavior into a pattern match:

s2 :: (a -> a -> b) -> [a] -> [b]
s2 f l = [ f a b | (a,b) <- zip (tail l) l ]


Hope that helps,

-Ross

On Apr 10, 2009, at 11:24 AM, michael rice wrote:

> All very neat, and it works! Thanks.
>
> But I copied
>
> map :: (a -> b) -> [a] -> [b]    <==  I'm assuming this is correct
>
> from something called "A Tour of the Haskell Prelude" at
>
> http://undergraduate.csse.uwa.edu.au/units/CITS3211/lectureNotes/tourofprelude.html#all
>
> which I was looking at to try and roll my own typing.
>
>
> My next question:
>
> My function
>
> s f ls
>
> seems much like
>
> map f ls
>
> but instead looks like
>
> s :: (a -> a -> a) -> [a] -> [a]
>
>
> Clearly, there's more to the picture than meets the eye. Is there a  
> good tutorial on types?
>
> Michael
>
>
> --- On Fri, 4/10/09, Joe Fredette <jfredett at gmail.com> wrote:
>
> From: Joe Fredette <jfredett at gmail.com>
> Subject: Re: [Haskell-cafe] Sequence differences
> To: "michael rice" <nowgate at yahoo.com>, "haskell Cafe mailing list" <haskell-cafe at haskell.org 
> >
> Date: Friday, April 10, 2009, 2:07 AM
>
> So, we can walk through it-
>
> >     s f [] = []
> >     s f [x] = [x]
> >     s f l = [ a f b | (a,b) <- zip (init l) (tail l)]
>
> First, we can write some of it to be a little more idiomatic, viz:
>
> s _ []  = []
> s _ [x] = [x]
> s f ls  = [f a b | (a,b) <- zip (init ls) (tail ls)]
>
> First, we have a function type, we can tell the variable f is a  
> function because it's applied to arguments in the third case, since  
> it's applied to two arguments, it's binary, so `s :: (a -> b -> c) - 
> > ?` however, from the
> second case, we know that whatever the type of the second argument  
> (a list of some type `a1`) is also the type
> of the return argument, since the `s` acts as the identity for lists  
> of length less than 2, so
>
>    s :: (a -> b -> a1) -> [a1] -> [a1]
>
> However, since the arguments for `f` are drawn from the same list,  
> the argument types must _also_ be of type `a1`, leaving us with:
>
>    s :: (a -> a -> a) -> [a] -> [a]
>
> This is, interestingly enough, precisely the type of foldr1.
>
> We can write your original function in another, cleaner way though,  
> too, since zip will "zip" to the smaller of the two lengths, so you  
> don't need to worry about doing the init and the tail, so `s` is  
> really:
>
> s _ []  = []
> s _ [x] = [x]
> s f ls  = [f a b | (a,b) <- zip ls (tail ls)]
>
> but there is a function which does precisely what the third case  
> does, called "zipWith" which takes a
> binary function and two lists and -- well -- does what that list  
> comprehension does. In fact, it does
> what your whole function does... In fact, it _is_ your function,  
> specialized a little, eg:
>
> yourZipWith f ls = zipWith f ls (tail ls)
>
>
> Hope that helps
>
> /Joe
>
> michael rice wrote:
> > I have a Scheme function that calculates sequence differences,  
> i.e., it returns a sequence that is the difference between the 2nd  
> and the 1st element, the 3rd and the 2nd, the 4th and the 3rd, etc.
> >
> > (define s
> >   (lambda (f l)
> >     (cond ((null? (cdr l)) '())
> >           (else (cons (f (cadr l) (car l))
> >                       (s f (cdr l)))))))
> >
> > where
> >
> > (s - '(0,1,3,6,10,15,21,28)) => (1,2,3,4,5,6,7)
> >
> >
> > I'm thinking the same function in Haskell would be something like
> >
> > s ::
> > s f [] = []
> > s f [x] = [x]
> > s f l = [ a f b | (a,b) <- zip (init l) (tail l)]
> >
> >
> > but can't figure out what the function typing would be.
> >
> > Michael
> >
> >
> >  
> ------------------------------------------------------------------------
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe