Genericity over tuples

One of Haskell's less elegant corners is the gaggle of zip functions specialized for tuples of different length (zip, zip2, zip3, etc..). Does anyone know what sort of language features would enable one to elegantly write a tuple agnostic zip function?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Zip Calculus

There's Mark Tullsen's Zip Calculus, designed for exactly that purpose.

Typed Scheme

Well, Scheme has for many years had a `map' function that handles arbitrary-arity functions. In Typed Scheme, we have some type system features that allow us to give a type to the full generality of `map'. You can see the documentation and examples for it here:

http://docs.plt-scheme.org/typed-scheme/index.html#(part._.Non-.Uniform_.Variable-.Arity_.Functions)

I don't totally understand

I don't totally understand how this works. When you write
"(map car bss)", what is the type of the non-uniform list 'bss'?

For example the type of '(4

For example the type of '(4 "hej hopp") would be (Listof (U Integer String)).

An explanation

In that expression, it's not really correct to say that `bss' has a "type", per se. You might think of its type as 'B ... B', however. That means that it's a list containing one element for each type that B gets instantiated with.

Does that help?

Do we Need Dependent

Do we Need Dependent Types?

Inspired by Danvy, we describe a technique for defining, within the Hindley-Milner type system, some functions which seem to require a language with dependent types. We illustrate this by giving a general definition of zipWith for which the Haskell library provides a family of functions, each member of the family having a different type and arity. Our technique consists in introducing ad hoc codings for natural numbers which resemble numerals in $\lambda$-calculus

Typing polyvariadic functions, including zipNWith

If we talk about polyvariadic functions like Scheme's map, it should
be pointed out that Haskell already can type them. It follows then
that Haskell supports polyvariadic zipWith.


http://okmij.org/ftp/Haskell/types.html#polyvar-fn

One perhaps has seen a recent Haskell-list thread on typed printf/scanf --
which are too naturally `polyvariadic'.

Neat

Wow, both this and the "Do we Need Dependent Types?" paper are very cool pieces of work. It never ceases to amaze me how much power/expressiveness can be squeezed out of the HM type system. Nonetheless, I was hoping to discover something a little more concise. Is there anything else of the same flavor as the 'Zip Calculus' Jeremy linked to?

A few points

First, do you have a definition of zipWith using the techniques described here? I've seen many encodings of a variadic zipWith in Haskell, all of which involve passing an encoding of the number of arguments as the first argument.

Second, while these functions are impressive, it's important to note that GHC still provides all of the numbered versions of zipWith, etc.

Generic Haskell and Template Meta Programming

The are tons of publications dealing with that matter, and even some implementations I think. What I get from it is that you basically have two choices: statically compute types and algorithms while using 'smart' templates (meta-haskell) or dynamically use the right algorithms by writing generic functions over types (generic extensions of Haskell).

I might be wrong on both accounts, this is not really my thing. If I can't read a program example in under five minutes, I usually think it is maybe academically interesting, but never will make it mainstream, so I stop reading. (Can't read everything, right?)

I guess a starting point would be: Template metaprogramming for Haskell

Arity-generic programming

Just posted to the dependent types subbreddit: Arity-Generic Datatype-Generic Programming. It's a paper using Agda's dependent typing to write "doubly-generic" functions which abstract over data type and arity, ie. repeat, map, zipWith, zipWith3, etc. are all the same function but with different arities.