{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}

-- This code implements a function with the variable number of
-- arguments and the matching variable type -- replacing an element in
-- a multi-dimensional list:
--   replace :: Int -> Int -> ... -> Int -> [..[e]..] -> e -> [..[e]..]
-- where 'e' is the type of list elements, and the number of index arguments
-- (of the type Int) must match the dimensionality of the list. In other
-- words, the code implements the function that has all of these signatures
--    replace :: e -> e -> e             -- replacing in a 0-dim list
--    replace :: Int -> [e] -> e -> [e]
--    replace :: Int -> Int -> [[e]] -> e -> [[e]]
--    replace :: Int -> Int -> Int -> [[[e]]] -> e -> [[[e]]]
--    ...
-- all at the same time.
-- This problem was posed as a `Type class puzzle' by Yitzchak Gale on
-- the Haskell-Cafe mailing list in Oct 2006.

-- This code is written by Chung-chieh Shan. Nov 12, 2006.
-- It is tested with GHC and Hugs -98. See Chung-chieh Shan's post
-- on Haskell-Cafe (Nov 12, 2006) for explanations.

module Puzzle where

class Replace'' n old new where
  repl'' :: n -> old -> new -> old

instance Replace'' () a a where
  repl'' () old new = new

instance Replace'' n old new => Replace'' (n,Int) [old] new where
  repl'' (i,i0) old new =
    case splitAt i0 old of (h,[]   ) -> h
                           (h,th:tt) -> h ++ repl'' i th new : tt

class Replace' n n' old new where
  repl' :: n -> n' -> old -> new -> old

instance Replace'' n old new => Replace' n () old new where
  repl' n () = repl'' n

instance Replace' (n1,n2) n3 old new => Replace' n1 (n2,n3) old new where
  repl' n1 (n2,n3) = repl' (n1,n2) n3

class Replace n a b c where
  repl :: n -> a -> b -> c

instance Replace' () n [old] new => Replace n [old] new [old] where
  repl = repl' ()

instance Replace (i,n) a b c => Replace n i a (b->c) where
  repl i0 i = repl (i,i0)

-- The desired function, whose inferred type is
--   replace :: (Replace () a b c) => a -> b -> c
replace n = repl () n


-- Tests

x1 = "abc"
x2 = ["ab", "cde", "fghi", "uvwxyz"]
x3 = [ [ [i1 + i2 + i3 | i3 <- [10..13]] | i2<- [4..5]] | i1 <- [(1::Int)..3]]

test1:: String
test1 = replace (1::Int) x1 'X'
-- "aXc"

{- expected error reported
test2:: [String]
test2 = replace (1::Int) x2 'X'
-}

test3:: [String]
test3 = replace (1::Int) x2 "X"
-- ["ab","X","fghi","uvwxyz"]

test4:: [String]
test4 = replace (2::Int) (1::Int) x2 'X'
-- ["ab","cde","fXhi","uvwxyz"]

test5:: [[[Int]]]
test5 = replace (2::Int) (0::Int) (1::Int) x3 (100::Int)
-- [[[15,16,17,18],[16,17,18,19]],[[16,17,18,19],[17,18,19,20]],
--  [[17,100,19,20],[18,19,20,21]]]