Haskell ST Monad: No instance for (MArray (STArray s) Int (ST s1)) -

i have been learning haskell past month or two, , solved this coding problem. additional challenge task without space , in linear time, did not think possible in purely functional way, naturally found out st monad , thought opportunity learn more it. anyways, here code wrote:

module findduplicates  import control.monad (foldm) import control.monad.st import data.array.st  xs = [4,3,2,7,8,2,3,1] :: [int]  findduplicates :: [int] -> st s [int] findduplicates xs =     arr <- newlistarray (1, length xs) xs :: st s (starray s int int)      let go :: [int] -> int -> st s [int]         go acc = x <- abs <$> readarray arr                       y <- readarray arr x                       if y < 0                           return (x:acc)                           else writearray arr x (-y)                                   return acc       foldm go [] [1..length xs] 

the idea use pre-condition 1 ≤ a[i] ≤ n , each element appears @ 2 times. code gives me following error.

findduplicates.hs:14:36:     no instance (marray (starray s) int (st s1))       arising use of ‘readarray’     in second argument of ‘(<$>)’, namely ‘readarray arr i’     in stmt of 'do' block: x <- abs <$> readarray arr     in expression:       { x <- abs <$> readarray arr i;            y <- readarray arr x;            if y < 0                return (x : acc)            else                { writearray arr x (- y);                     .... } } 

i hope can point me in right direction!

in no instance (marray (starray s) int (st s1)), important thing notice it's talking 2 different type variables, s , s1. there no instance of marray unless 2 type variables same. important part of how st valid externally-pure interface.

the reason compiler thinks there 2 different type variables involved put type signature on go. type variable s in signature not same type variable s in signature of findduplicates. inherent part of haskell's type signature rules - type variables in particular signature unrelated type variables in other signature.

the simplest way fix remove signature go. type inference correct type it.

if want fancier, can use scopedtypevariables extension allow signature on go share type variable enclosing definition:

{-# language scopedtypevariables #-} module findduplicates  import control.monad (foldm) import control.monad.st import data.array.st  xs = [4,3,2,7,8,2,3,1] :: [int]  findduplicates :: forall s. [int] -> st s [int] findduplicates xs =     arr <- newlistarray (1, length xs) xs :: st s (starray s int int)      let go :: [int] -> int -> st s [int]         go acc = x <- abs <$> readarray arr                       y <- readarray arr x                       if y < 0                           return (x:acc)                           else writearray arr x (-y)                                   return acc       foldm go [] [1..length xs] 

the language pragma @ top enables extension. use extension, need specify type variables in definition forall. (forgetting common reason scopedtypevariables fail work.)

after doing in type of findduplicates, stores s in scope across entire definition. when finding type variable s in type of go, no longer treats fresh type variable, , makes match type s in enclosing context instead.