Hi, I’m currently playing with the mutable array to implement an heap sort sort (from The Art of Computer Programming) and I’m puzzled with an error. When I code: toHeap :: Ord a => [a] -> IO [a] toHeap [] = return [] toHeap [x] = return [x] toHeap xs = do arr <- newListArray (1, length xs) xs :: IO (IOArray Int a) getElems arr I’ve got this error: Could not deduce (a ~ a1) from the context (Ord a) bound by the type signature for toHeap :: Ord a => [a] -> IO [a] at /var/folders/fk/339860r16j759wmsfmjkyr4h0000gn/T/flycheck797T5s/Heapsort.hs:9:11-32 ‘a’ is a rigid type variable bound by the type signature for toHeap :: Ord a => [a] -> IO [a] at /var/folders/fk/339860r16j759wmsfmjkyr4h0000gn/T/flycheck797T5s/Heapsort.hs:9:11 ‘a1’ is a rigid type variable bound by an expression type signature: IO (IOArray Int a1) at /var/folders/fk/339860r16j759wmsfmjkyr4h0000gn/T/flycheck797T5s/Heapsort.hs:14:10 Expected type: [a1] Actual type: [a] Relevant bindings include xs :: [a] (bound at /var/folders/fk/339860r16j759wmsfmjkyr4h0000gn/T/flycheck797T5s/Heapsort.hs:12:8) toHeap :: [a] -> IO [a] (bound at /var/folders/fk/339860r16j759wmsfmjkyr4h0000gn/T/flycheck797T5s/Heapsort.hs:10:1) In the second argument of ‘newListArray’, namely ‘xs’ In a stmt of a 'do' block: arr <- newListArray (1, length xs) xs :: IO (IOArray Int a) But with the code below, all work: toHeap :: Ord a => [a] -> IO [a] toHeap [] = return [] toHeap [x] = return [x] toHeap xs = do arr <- buildArray xs getElems arr buildArray :: [a] -> IO (IOArray Int a) buildArray xs = newListArray (1, length xs) xs What do I miss ? Thanks. Chris
On Sun, Apr 12, 2015 at 12:41 PM, Christian Sperandio < christian.sperandio@gmail.com> wrote:
I’m currently playing with the mutable array to implement an heap sort sort (from The Art of Computer Programming) and I’m puzzled with an error.
When I code:
toHeap :: Ord a => [a] -> IO [a] toHeap [] = return [] toHeap [x] = return [x] toHeap xs = do arr <- newListArray (1, length xs) xs :: IO (IOArray Int a) getElems arr
Note that the "a" in the signature "IO (IOArray Int a)" is *not* the same as the one in the signature of toHeap; the scope of that type variable is the signature itself, not the following equation(s). You have in effect done the opposite of what you intended --- instead of asserting it is the same, you asserted that it is a *different* one, by handing the compiler an unexpected `a` which must be assumed to represent a distinct type. If you need to extend the scope of a type variable like this, you need the ScopedTypeVariables extension, and to declare the type variable as having extended scope with an explicit `forall`: {-# LANGUAGE ScopedTypeVariables #-} toHeap :: forall a. Ord a => [a] -> IO [a] toHeap [] = return [] toHeap [x] = return [x] toHeap xs = do arr <- newListArray (1, length xs) xs :: IO (IOArray Int a) getElems arr -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
participants (2)
-
Brandon Allbery -
Christian Sperandio