I have been learning Haskell for the past month or two, and recently solved this coding problem. The additional challenge was to do the task without extra space and in linear time, which I did not think would be possible to do in a purely functional way, so naturally I found out about the ST monad and I thought this would be a good opportunity to learn more about it. Anyways, here is the code that I wrote:
module FindDuplicates where
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 = do
arr <- newListArray (1, length xs) xs :: ST s (STArray s Int Int)
let go :: [Int] -> Int -> ST s [Int]
go acc i = do x <- abs <$> readArray arr i
y <- readArray arr x
if y < 0
then return (x:acc)
else do writeArray arr x (-y)
return acc
foldM go [] [1..length xs]
The idea is to use the pre-condition that 1 ≤ a[i] ≤ n and that each element appears at most 2 times. But the code gives me the following error.
FindDuplicates.hs:14:36:
No instance for (MArray (STArray s) Int (ST s1))
arising from a use of ‘readArray’
In the second argument of ‘(<$>)’, namely ‘readArray arr i’
In a stmt of a 'do' block: x <- abs <$> readArray arr i
In the expression:
do { x <- abs <$> readArray arr i;
y <- readArray arr x;
if y < 0 then
return (x : acc)
else
do { writeArray arr x (- y);
.... } }
I hope someone can point me in the right direction!
In No instance for (MArray (STArray s) Int (ST s1)), the most important thing to notice is that it's talking about two different type variables, s and s1. There is no instance of MArray unless those two type variables are the same. This is an important part of how ST is valid with an externally-pure interface.
The reason the compiler thinks that there are two different type variables involved is that you put a type signature on go. The type variable s in that signature is not the same as the type variable s in the signature of findDuplicates. This is an inherent part of Haskell's type signature rules - type variables in any particular signature are unrelated to type variables in any other signature.
The simplest way to fix this is to remove the signature from go. Type inference will get the correct type for it.
If you want to get fancier, you can use the ScopedTypeVariables extension to allow the signature on go to share the type variable with the enclosing definition:
{-# LANGUAGE ScopedTypeVariables #-}
module FindDuplicates where
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 = do
arr <- newListArray (1, length xs) xs :: ST s (STArray s Int Int)
let go :: [Int] -> Int -> ST s [Int]
go acc i = do x <- abs <$> readArray arr i
y <- readArray arr x
if y < 0
then return (x:acc)
else do writeArray arr x (-y)
return acc
foldM go [] [1..length xs]
The LANGUAGE pragma at the top enables the extension. To use the extension, you need to specify the type variables in a definition with forall. (Forgetting to do that is the most common reason for ScopedTypeVariables to fail to work.)
After doing that in the type of findDuplicates, it stores that s in scope across the entire definition. When finding the type variable s in the type of go, it no longer treats it as a fresh type variable, and makes it match the type s in the enclosing context instead.