[Haskell-cafe] generics question, logical variables

Yitzchak Gale gale at sefer.org
Mon Sep 19 05:20:32 EDT 2005

Ralf Lammel wrote:

> Does anyone want to speak up and mention
> scenarios that would benefit from kind
> polymorphism? (In Haskell, we are likely to see
> kind polymorphism, if at all, in the form of
> type classes whose type parameters can be of
> different, perhaps of all kinds.)

Here are two possible simple examples.

The first is from "real life": I once needed a
polymorphic function "replace" that replaces an
element of an n-dimensional list given its
coordinates and a replacement value:

replace :: Int -> a -> [a] -> [a]
replace :: Int -> Int -> a -> [[a]] -> [[a]]

Also, trivially, in dimension zero:

replace :: a -> a -> a

So we have:

dim 0: replace = const

dim 1: replace i x (y:ys)
        | i == 0    = replace x y : ys
        | otherwise = y : replace (i-1) x ys
       replace _ _ _ = []

dim 2: replace i j x (y:ys)
        | i == 0    = replace j x y : ys
        | otherwise = y : replace (i-1) j x ys
       replace _ _ _ _ = []


Intuitively, this ought to be simple. But I leave
it as an exercise for the reader to implement it
using the current type system. What a mess!

Second example:

It seems intuitive that the State monad should
be isomorphic to the lazy ST monad with STRef, in
the sense that it should be possible to implement
each monad in terms of the other.

(For the purpose of this discussion, let us ignore
differences in strictness due to the execution
strategies of any given compiler, though that also
may be an interesting topic.)

Well, in one direction that is trivial - it is easy
to implement State using lazy ST and STRef.

As for the other direction - yuck! Again, I leave
it as an exercise for the reader.


More information about the Haskell-Cafe mailing list