[Haskell-cafe] Sequence differences
Ross Mellgren
rmm-haskell at z.odi.ac
Fri Apr 10 12:36:16 EDT 2009
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
More information about the Haskell-Cafe
mailing list