Sequence differences

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Sequence differences

michael rice-3
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

jfredett
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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>  

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

jfredett.vcf (308 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

michael rice-3
In reply to this post by michael rice-3
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 <[hidden email]> wrote:

From: Joe Fredette <[hidden email]>
Subject: Re: [Haskell-cafe] Sequence differences
To: "michael rice" <[hidden email]>, "haskell Cafe mailing list" <[hidden email]>
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@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>   

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

Martijn van Steenbergen-2
Hi Michael,

michael rice wrote:
> Clearly, there's more to the picture than meets the eye. Is there a good
> tutorial on types?

Have you seen Real World Haskell?

http://book.realworldhaskell.org/read/

Chapter 2 already dives into types.

Hope this helps,

Martijn.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

jfredett
In reply to this post by michael rice-3
You might try looking at Real World Haskell, it's not so much a tutorial
on types, but a tutorial on Haskell in general. Theres also the
Haskell-beginner's list, the backlogs of which are quite nice. Really
the best way to learn is to just dive in, you can use Hoogle or Hayoo to
search APIs. Just try to come up with a good idea, and start working on it!

And of course, you can ask questions here or on Haskell-beginners. The
rumors are true, we're awesome people.

/Joe

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 /<[hidden email]>/* wrote:
>
>
>     From: Joe Fredette <[hidden email]>
>     Subject: Re: [Haskell-cafe] Sequence differences
>     To: "michael rice" <[hidden email]>, "haskell Cafe mailing
>     list" <[hidden email]>
>     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
>     > [hidden email] </mc/compose?to=[hidden email]>
>     > http://www.haskell.org/mailman/listinfo/haskell-cafe
>     >  
>
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

jfredett.vcf (308 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

Chad Scherrer-2
In reply to this post by jfredett
Joe Fredette <jfredett <at> gmail.com> writes:

> 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)

A nice generalization of this that can be really useful is

movingWindow :: Int -> [a] -> [[a]]
movingWindow 1 xs = map (:[]) xs
movingWindow n xs = zipWith (:) xs . tail $ movingWindow (n-1) xs

So for example,

> movingWindow 3 [1..10]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]]

Then you can write

diff :: (Num a) => [a] -> [a]
diff = map (\[x,y] -> y - x) . movingWindow 2

Hopefully the intermediate lists are optimized away, but I haven't done any
performance testing.

Chad

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

Ross Mellgren
In reply to this post by michael rice-3
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 <[hidden email]> wrote:
>
> From: Joe Fredette <[hidden email]>
> Subject: Re: [Haskell-cafe] Sequence differences
> To: "michael rice" <[hidden email]>, "haskell Cafe mailing list" <[hidden email]
> >
> 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
> > [hidden email]
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

michael rice-3
In reply to this post by michael rice-3
No, I was unaware of this, but it looks good.

Thanks.

Michael

--- On Fri, 4/10/09, Martijn van Steenbergen <[hidden email]> wrote:

From: Martijn van Steenbergen <[hidden email]>
Subject: Re: [Haskell-cafe] Sequence differences
To: "michael rice" <[hidden email]>
Cc: "haskell Cafe mailing list" <[hidden email]>, "Joe Fredette" <[hidden email]>
Date: Friday, April 10, 2009, 11:38 AM

Hi Michael,

michael rice wrote:
> Clearly, there's more to the picture than meets the eye. Is there a good tutorial on types?

Have you seen Real World Haskell?

http://book.realworldhaskell.org/read/

Chapter 2 already dives into types.

Hope this helps,

Martijn.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

Ketil Malde-5
In reply to this post by michael rice-3
michael rice <[hidden email]> writes:

> map :: (a -> b) -> [a] -> [b]    <==  I'm assuming this is correct

This is the type of 'map', yes.  Btw, ou can check types in GHCi with the
:i command.

> s f ls
>
> seems much like
>
> map f ls
>
> but instead looks like  
>
> s :: (a -> a -> a) -> [a] -> [a]

If you look at the definition:

>> s f [] = []
>> s f [x] = [x]
>> s f l = [ a f b | (a,b) <- zip (init l) (tail l)]

You'll notice that the second clause, namely

   s f [x] = [x]

produces the second parameter [x] (of type [a]) as its output, and
thus the types must be the same as well.

Also (assuming it is 'f a b' and not 'a f b' in the list
comprehension), f is applied to two parameters, so it'll have to be
of type (x -> y -> z), and since the two input parameters come from
the originating list, x and y must be the same as a, and since we have
seen the result list also has the same type, z must be the same as a,
too.  Thus f must have type (a -> a -> a).  Unclear? Clear? Operating
thetan?

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Sequence differences

michael rice-3
In reply to this post by michael rice-3
Yes, that is nice, and also useful for calculating moving averages.

Thanks.

Michael

--- On Fri, 4/10/09, Chad Scherrer <[hidden email]> wrote:

From: Chad Scherrer <[hidden email]>
Subject: [Haskell-cafe] Re: Sequence differences
To: [hidden email]
Date: Friday, April 10, 2009, 12:04 PM

Joe Fredette <jfredett <at> gmail.com> writes:

> 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)

A nice generalization of this that can be really useful is

movingWindow :: Int -> [a] -> [[a]]
movingWindow 1 xs = map (:[]) xs
movingWindow n xs = zipWith (:) xs . tail $ movingWindow (n-1) xs

So for example,

> movingWindow 3 [1..10]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]]

Then you can write

diff :: (Num a) => [a] -> [a]
diff = map (\[x,y] -> y - x) . movingWindow 2

Hopefully the intermediate lists are optimized away, but I haven't done any
performance testing.

Chad

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sequence differences

michael rice-3
In reply to this post by michael rice-3
Clearly, I have some reading to do.

Thanks,

Michael

--- On Fri, 4/10/09, Ketil Malde <[hidden email]> wrote:

From: Ketil Malde <[hidden email]>
Subject: Re: [Haskell-cafe] Sequence differences
To: "michael rice" <[hidden email]>
Cc: "haskell Cafe mailing list" <[hidden email]>, "Joe Fredette" <[hidden email]>
Date: Friday, April 10, 2009, 3:52 PM

michael rice <nowgate@...> writes:

> map :: (a -> b) -> [a] -> [b]    <==  I'm assuming this is correct

This is the type of 'map', yes.  Btw, ou can check types in GHCi with the
:i command.

> s f ls
>
> seems much like
>
> map f ls
>
> but instead looks like  
>
> s :: (a -> a -> a) -> [a] -> [a]

If you look at the definition:

>> s f [] = []
>> s f [x] = [x]
>> s f l = [ a f b | (a,b) <- zip (init l) (tail l)]

You'll notice that the second clause, namely

   s f [x] = [x]

produces the second parameter [x] (of type [a]) as its output, and
thus the types must be the same as well.

Also (assuming it is 'f a b' and not 'a f b' in the list
comprehension), f is applied to two parameters, so it'll have to be
of type (x -> y -> z), and since the two input parameters come from
the originating list, x and y must be the same as a, and since we have
seen the result list also has the same type, z must be the same as a,
too.  Thus f must have type (a -> a -> a).  Unclear? Clear? Operating
thetan?

-k
--
If I haven't seen further, it is by standing in the footprints of giants


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Sequence differences

Henning Thielemann
In reply to this post by Chad Scherrer-2

On Fri, 10 Apr 2009, Chad Scherrer wrote:

> A nice generalization of this that can be really useful is
>
> movingWindow :: Int -> [a] -> [[a]]
> movingWindow 1 xs = map (:[]) xs
> movingWindow n xs = zipWith (:) xs . tail $ movingWindow (n-1) xs
>
> So for example,
>
>> movingWindow 3 [1..10]
> [[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]]


movingWindow n xs =
    take (length xs - n +1) $ map (take n) $ tails xs

or more efficient using utility-ht package:

movingWindow n xs =
    Data.List.Match.take (drop (n-1) xs) $
       map (take n) $ tails xs


> Then you can write
>
> diff :: (Num a) => [a] -> [a]
> diff = map (\[x,y] -> y - x) . movingWindow 2
>
> Hopefully the intermediate lists are optimized away, but I haven't done any
> performance testing.

I'm not sure. You are safer and more efficient when you restrict to pairs.
Since I often need the function, I defined:
   http://hackage.haskell.org/packages/archive/utility-ht/0.0.4/doc/html/Data-List-HT.html#v%3AmapAdjacent

Then
   diff = mapAdjacent subtract
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

RE: Re: Sequence differences

Chad Scherrer-2
 
henning thielmann writes:

> movingWindow n xs =
>     take (length xs - n +1) $ map (take n) $ tails xs
>
> or more efficient using utility-ht package:
>
> movingWindow n xs =
>     Data.List.Match.take (drop (n-1) xs) $
>        map (take n) $ tails xs

Oh, very nice. I was a little frustrated writing the recursion
explicitly. I guess you could also write

movingWindow n xs = zipWith const (map (take n) $ tails xs) $ drop (n-1)
xs

Hmm, maybe this is obvious, if

Data.List.Match.take == zipWith (flip const)

(I've never used it)
 
> I'm not sure. You are safer and more efficient when you
> restrict to pairs.
> Since I often need the function, I defined:
>    
> http://hackage.haskell.org/packages/archive/utility-ht/0.0.4/d
oc/html/Data-List-HT.html#v%3AmapAdjacent
>
> Then
>    diff = mapAdjacent subtract

Yes, I agree if you know you'll be using a binary operator, and not a
more general n-ary function.

Chad
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe