[Haskell] Help in understanding a type error involving forall and
class constraints
MR K P SCHUPKE
k.schupke at imperial.ac.uk
Tue Jun 29 13:42:19 EDT 2004
Erm, something I remember about needing MArrays... Here's something
which does the same thing (cooks and MArray then freezes it - also using
STUArray... The neat thing is MArray is a class, so you can swap between
STUArray and STArray implementations without changing code.
This is the classic dynamic programming version of string difference:
distString :: String -> String -> Int
distString s0 s1 = runST (difST s0 s1)
difST :: MArray (STUArray s) Int (ST s) => String -> String -> ST s Int
difST s0 s1 = do
b@(_,br) <- return $ (\x1 y1 -> ((0,0),(x1,y1))) (length s0) (length s1)
d <- newArray b 0 :: ST s (STUArray s (Int,Int) Int)
mdiff d s0 s1
readArray d br
mMin :: Int -> Int -> Int -> Int
mMin i j k = min (min i j) k
costDelete :: Char -> Int
costDelete _ = 1
costInsert :: Char -> Int
costInsert _ = 1
costReplace :: Char -> Char -> Int
costReplace _ _ = 1
mdiff :: MArray a Int m => a (Int,Int) Int -> String -> String -> m ()
mdiff (d :: a e i) s0 s1 = do
writeArray d (0,0) 0
foreach 1 s0 $ \x a -> do
dx <- readArray d (x-1,0)
writeArray d (x,0) (dx+costDelete a)
foreach 1 s1 $ \y b -> do
dy <- readArray d (0,y-1)
writeArray d (0,y) (dy+costInsert b)
foreach 1 s0 $ \x a -> do
foreach 1 s1 $ \y b -> do
dx <- readArray d (x-1,y)
dy <- readArray d (x,y-1)
dxy <- readArray d (x-1,y-1)
writeArray d (x,y) $ mMin (dx+costDelete a) (dy+costInsert b)
(if a==b then dxy else dxy+costReplace a b)
where
foreach :: MArray a Int m => Int -> String -> (Int -> Char -> m ()) -> m ()
foreach _ [] _ = return ()
foreach i (c0:cs) f = do
f i c0
foreach (i+1) cs f
------------------------------------
Keean.
More information about the Haskell
mailing list