zip3, zip4 ... -> zipn?

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

zip3, zip4 ... -> zipn?

Frank Buss
Is it possible to write a function like this:

zipn n list_1 list_2 list_3 ... list_n

which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number
of arguments are possible, like printf shows, so a general zipn should be
possible, too. If it is possible, why there are functions like zip5 and not
just zipn?

--
Frank Buss, [hidden email]
http://www.frank-buss.de, http://www.it4-systems.de

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

Re: zip3, zip4 ... -> zipn?

Joel Koerwer-2
Frank,

The return type of zipn would have to depend on the number of
arguments. If you are satisfied with all arguments having the same
type, then you can use transpose:

zipn list1 list2 .. listn  => transpose [list1, list2, .. listn]

Can we make a polyvariadic zipn that returns a [HList]? Seems like a
neat challenge, but I'm a bit pressed for time right now. I'm afraid
it would be pretty unwieldy.

I'm looking forward to seeing solutions though. :-)

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

Re: zip3, zip4 ... -> zipn?

Hugh Perkins
I was looking for something like this too.

Note that Erlang can do this ;-)  but Erlang is probably not so
strongly typed, so it's easier to do?
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: zip3, zip4 ... -> zipn?

Heinrich Apfelmus
In reply to this post by Frank Buss
Frank Buss schrieb:
> Is it possible to write a function like this:
>
> zipn n list_1 list_2 list_3 ... list_n
>
> which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number
> of arguments are possible, like printf shows, so a general zipn should be
> possible, too. If it is possible, why there are functions like zip5 and not
> just zipn?

What type would this function have? It's not possible to formulate this
type in Haskell98. The problem is that the number of arguments cannot be
determined statically, i.e. it depends on the value of  n  at run-time.
There are languages more freaky than Haskell (like Agda or Epigram )
that can do that (without dynamic typing, that is!), they are called
"dependently typed".

However, type-class hackery (or type synonym families once they're
available in GHC) can be used to do something like that if you give the
value of n at compile-time. I won't dwell into that, though.

Also, applicative functors can help

   GHCi> :m +Control.Applicative
   GHCi> (\x y z -> x*(y+z)) <$> ZipList [1,2,3]
         <*> ZipList [-1,0,1] <*> ZipList [1,1,1]
   ZipList [0,2,6]
   GHCi>

(the second command is a single line.)

Regards,
apfelmus

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

Re: zip3, zip4 ... -> zipn?

Brent Yorgey
In reply to this post by Frank Buss

On 8/11/07, Frank Buss <[hidden email]> wrote:
Is it possible to write a function like this:

zipn n list_1 list_2 list_3 ... list_n

which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number
of arguments are possible, like printf shows, so a general zipn should be
possible, too. If it is possible, why there are functions like zip5 and not
just zipn?

Template Haskell can also be used to generate appropriate code for zipn (in fact, the original paper on TH even uses this as an example [1]).  But again, this approach only works if the value of n is known at compile time.

-Brent

[1] http://www.haskell.org/th/papers/meta-haskell.ps

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

Re: Re: zip3, zip4 ... -> zipn?

Per Vognsen
In reply to this post by Heinrich Apfelmus
On 8/11/07, apfelmus <[hidden email]> wrote:

> Frank Buss schrieb:
> > Is it possible to write a function like this:
> >
> > zipn n list_1 list_2 list_3 ... list_n
> >
> > which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number
> > of arguments are possible, like printf shows, so a general zipn should be
> > possible, too. If it is possible, why there are functions like zip5 and not
> > just zipn?
>
> What type would this function have? It's not possible to formulate this
> type in Haskell98. The problem is that the number of arguments cannot be
> determined statically, i.e. it depends on the value of  n  at run-time.
> There are languages more freaky than Haskell (like Agda or Epigram )
> that can do that (without dynamic typing, that is!), they are called
> "dependently typed".
>
> However, type-class hackery (or type synonym families once they're
> available in GHC) can be used to do something like that if you give the
> value of n at compile-time. I won't dwell into that, though.
>
> Also, applicative functors can help
>
>    GHCi> :m +Control.Applicative
>    GHCi> (\x y z -> x*(y+z)) <$> ZipList [1,2,3]
>          <*> ZipList [-1,0,1] <*> ZipList [1,1,1]
>    ZipList [0,2,6]
>    GHCi>
>
> (the second command is a single line.)

Applicative functors can indeed help:

    (,,,) <$> [1,2,3] <*> [-1,0,1] <*> [1,1,1] <*> [0,2,6]

You just use n-1 commas when you want the effect of zipn.

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

Re: zip3, zip4 ... -> zipn?

Chung-chieh Shan-2
In reply to this post by Frank Buss
Frank Buss <[hidden email]> wrote in article <0e3d01c7dbed$59676970$64c5a8c0@galilei> in gmane.comp.lang.haskell.cafe:
> Is it possible to write a function like this:
>
> zipn n list_1 list_2 list_3 ... list_n
>
> which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number
> of arguments are possible, like printf shows, so a general zipn should be
> possible, too. If it is possible, why there are functions like zip5 and not
> just zipn?

Check out:

Fridlender, Daniel, and Mia Indrika. 2000. Do we need dependent
types? Journal of Functional Programming 10(4):409-415.
http://www.math.chalmers.se/~indrika/jfp.ps.gz

McBride, Conor. 2002. Faking it: Simulating dependent types in
Haskell. Journal of Functional Programming 12(4-5): 375-392.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
Remember Hirosima 1945-08-06, Nagasaki 1945-08-09.
http://petitions.pm.gov.uk/Free-Vanunu/ http://www.vanunu.org/

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

Re: zip3, zip4 ... -> zipn?

Stefan O'Rear
In reply to this post by Hugh Perkins
On Sat, Aug 11, 2007 at 05:27:19PM +0800, Hugh Perkins wrote:
> I was looking for something like this too.
>
> Note that Erlang can do this ;-)  but Erlang is probably not so
> strongly typed, so it's easier to do?

I think the main issue is that Erlang doesn't use currying (IIRC).
Currying makes it MUCH harder to implement varargs functions.  (We
thought this was a good tradeoff - partial applications give Haskell
much more power than varargs would have.)

(Unfortunately I don't know of any good languages with powerful type
systems and vararg functions that can take advantage of powerful
types...  I'd love to give example code here :))

Stefan

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

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Re: zip3, zip4 ... -> zipn?

Marc Weber
In reply to this post by Heinrich Apfelmus
> Also, applicative functors can help
>
>   GHCi> :m +Control.Applicative
>   GHCi> (\x y z -> x*(y+z)) <$> ZipList [1,2,3]
>         <*> ZipList [-1,0,1] <*> ZipList [1,1,1]
>   ZipList [0,2,6]
>   GHCi>
http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf
quote "The general scheme is as follows:"
(page 2)

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

Re: zip3, zip4 ... -> zipn?

Alexis Hazell
In reply to this post by Stefan O'Rear
On Sunday 12 August 2007 05:24, Stefan O'Rear wrote:

> Currying makes it MUCH harder to implement varargs functions.

That's interesting - why is that the case?


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

Re: zip3, zip4 ... -> zipn?

Stefan O'Rear
On Sun, Aug 12, 2007 at 12:56:31PM +1000, Alexis Hazell wrote:
> On Sunday 12 August 2007 05:24, Stefan O'Rear wrote:
>
> > Currying makes it MUCH harder to implement varargs functions.
>
> That's interesting - why is that the case?

varsum 2 3   -- varsum receives 2, and returns a function, which when
             -- passed 3, returns 5
varsum 2 3 4 -- varsum receives 2, and returns a function, which when
             -- passed 3, returns a function that when passed 4 returns
             -- 9.

Because of this, the number of arguments must somehow be passed
out-of-band; but then the type of the whole function (usually) must
depend on the control parameter, requiring dependent types.

Stefan

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

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: zip3, zip4 ... -> zipn?

Tomasz Zielonka
In reply to this post by Frank Buss
On Sat, Aug 11, 2007 at 09:58:05AM +0200, Frank Buss wrote:
> Is it possible to write a function like this:
>
> zipn n list_1 list_2 list_3 ... list_n
>
> which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number
> of arguments are possible, like printf shows, so a general zipn should be
> possible, too. If it is possible, why there are functions like zip5 and not
> just zipn?

I prefer to do n-ary zips this way:

    zipApply = zipWith ($)

    x = repeat (,,) `zipApply` [1,2,3] `zipApply` ["a", "bc", "de"] `zipApply` [1.0, 1.2..]

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

Re: varsum, was zip3, zip4 ... -> zipn?

Conor McBride
In reply to this post by Stefan O'Rear
Hi Stefan

I'd have my membership of the one-leg club taken away if I didn't
write in and say that,...

On 12 Aug 2007, at 04:25, Stefan O'Rear wrote:

> On Sun, Aug 12, 2007 at 12:56:31PM +1000, Alexis Hazell wrote:
>> On Sunday 12 August 2007 05:24, Stefan O'Rear wrote:
>>
>>> Currying makes it MUCH harder to implement varargs functions.

...while I wouldn't disagree,...


>>>
>>
>> That's interesting - why is that the case?
>
> varsum 2 3   -- varsum receives 2, and returns a function, which when
>              -- passed 3, returns 5
> varsum 2 3 4 -- varsum receives 2, and returns a function, which when
>              -- passed 3, returns a function that when passed 4  
> returns
>              -- 9.

...this is one of the more elementary exercises in overloading...

>
> Because of this, the number of arguments must somehow be passed
> out-of-band;

...the type...

> but then the type of the whole function (usually) must
> depend on the control parameter, requiring dependent types.

...of dependent walk you can mimic by hopping in Haskell.

 > module VarSum where

 > class VarSum t where
 >   varacc :: Int -> t

 > varsum :: VarSum t => t
 > varsum = varacc 0

 > type Z = Int
 > type S = (->) Int

 > instance VarSum Z where
 >   varacc a = a

 > instance VarSum t => VarSum (S t) where
 >   varacc a b = varacc (a + b)

Of course, you have to say stuff like

   varsum (2 :: Int) (3 :: Int) :: Int

to determine the type at which the overloading happens. Or perhaps

   (varsum :: S (S Z)) 2 3

But there am I, proving your point. In Haskell, this sort of thing
is a stunt. I'd much rather it was boring.

All the best

Conor

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

Re: Re: zip3, zip4 ... -> zipn?

Brent Yorgey
In reply to this post by Per Vognsen

On 8/11/07, Per Vognsen <[hidden email]> wrote:
Applicative functors can indeed help:

    (,,,) <$> [1,2,3] <*> [-1,0,1] <*> [1,1,1] <*> [0,2,6]

You just use n-1 commas when you want the effect of zipn.

Actually, that's not quite right, since that uses the applicative functor related to the list monad (so you get a list of 4-tuples of all possible combinations, rather than a 4-way zip).  To get the zip behavior, you need to add a ZipList constructor in front of all the lists, and then apply getZipList at the end to extract.

-Brent

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