Home » forums » LtU Forum

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?

By Alex Rubinsteyn at 2008-09-18 03:55 | LtU Forum | previous forum topic | next forum topic | other blogs | 10855 reads

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.

By Jeremy at Thu, 2008-09-18 08:25 | login or register to post comments

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)

By Sam Tobin-Hochstadt at Thu, 2008-09-18 15:28 | login or register to post comments

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'?

By Alex Rubinsteyn at Fri, 2008-09-19 18:39 | login or register to post comments

For example the type of '(4

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

By Felicia Li Svilling at Fri, 2008-09-19 18:52 | login or register to post comments

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?

By Sam Tobin-Hochstadt at Tue, 2008-09-23 13:07 | login or register to post comments

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

By Gal Amram at Thu, 2008-09-18 16:06 | login or register to post comments

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'.

By Oleg at Thu, 2008-09-18 23:19 | login or register to post comments

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?

By Alex Rubinsteyn at Fri, 2008-09-19 18:47 | login or register to post comments

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.

By Sam Tobin-Hochstadt at Tue, 2008-09-23 13:23 | login or register to post comments

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

By marco at Tue, 2008-09-23 15:55 | login or register to post comments

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.

By naasking at Wed, 2010-02-03 21:04 | login or register to post comments