[Haskell-cafe] Sequence differences

Joe Fredette jfredett at gmail.com
Fri Apr 10 02:07:12 EDT 2009


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
>   
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jfredett.vcf
Type: text/x-vcard
Size: 296 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090410/020793dc/jfredett.vcf


More information about the Haskell-Cafe mailing list