[Haskell-cafe] A type class puzzle

[Tomasz Zielonka]

On Tue, Oct 31, 2006 at 11:02:03AM +0200, Yitzchak Gale wrote:
> Consider the following sequence of functions
> that replace a single element in an n-dimensional
> list:
> 
> replace0 :: a -> a -> a
> replace1 :: Int -> a -> [a] -> [a]
> replace2 :: Int -> Int -> a -> [[a]] -> [[a]]

> Generalize this using type classes.

It's quite easy if you allow the indices to be put in a single compound
value. If you insist that each index should be given as a separate
function argument, it may be possible to achieve it using the tricks
that allow to write the variadic composition operator.

Here's my version using MPTCs and fundeps:

    data Index t = I Int t

    class Replace i l a | i a -> l where
        replace :: i -> a -> l -> l

    instance Replace () a a where
        replace _ = const

    instance Replace i l a => Replace (Index i) [l] a where
        replace (I i0 is) x xs
            | null t    = h
            | otherwise = h ++ (replace is x (head t) : tail t)
          where (h, t) = splitAt i0 xs

Example use:

    *Nested> :t replace (I 0 $ I 2 $ I 3 $ ()) "qweqwe"
    replace (I 0 $ I 2 $ I 3 $ ()) "qweqwe" :: [[[[Char]]]] -> [[[[Char]]]]


Best regards
Tomasz