2

I have written 2 Haskell functions: 

unfold nhs xs | val == Nothing = []
              | otherwise      = b:unfold nhs a
   where val = nhs xs
         Just (b, a) = val

extractMin [] = Nothing
extractMin (x:xs) | val == Nothing || b > x = Just (x, xs)
                  | otherwise = Just (b, x:a)
   where val = extractMin xs
         Just (b, a) = val

The first one is essentially unfoldr from Data.List, and the second one takes a list and returns a Maybe tuple consisting of the minimum element and the rest of the list. Both functions seem to be working properly.

Applying extractMin to unfold is supposed to produce selection sort. However, here I have noticed some strange behavior. If I define selection sort as:

ssort = unfold extractMin

the compiler throws an error:

test.hs:13:10:
    No instance for (Eq t0) arising from a use of ‘unfold’
    The type variable ‘t0’ is ambiguous
    Relevant bindings include
      ssort' :: [t0] -> [t0] (bound at test.hs:13:1)
    Note: there are several potential instances:
      instance (Eq a, Eq b) => Eq (Either a b)
        -- Defined in ‘Data.Either’
      instance forall (k :: BOX) (s :: k). Eq (Data.Proxy.Proxy s)
        -- Defined in ‘Data.Proxy’
      instance (GHC.Arr.Ix i, Eq e) => Eq (GHC.Arr.Array i e)
        -- Defined in ‘GHC.Arr’
      ...plus 28 others
    In the expression: unfold extractMin
    In an equation for ‘ssort'’: ssort' = unfold extractMin

test.hs:13:17:
    No instance for (Ord t0) arising from a use of ‘extractMin’
    The type variable ‘t0’ is ambiguous
    Relevant bindings include
      ssort' :: [t0] -> [t0] (bound at test.hs:13:1)
    Note: there are several potential instances:
      instance (Ord a, Ord b) => Ord (Either a b)
        -- Defined in ‘Data.Either’
      instance forall (k :: BOX) (s :: k). Ord (Data.Proxy.Proxy s)
        -- Defined in ‘Data.Proxy’
      instance (GHC.Arr.Ix i, Ord e) => Ord (GHC.Arr.Array i e)
        -- Defined in ‘GHC.Arr’
      ...plus 27 others
    In the first argument of ‘unfold’, namely ‘extractMin’
    In the expression: unfold extractMin
    In an equation for ‘ssort'’: ssort' = unfold extractMin
Failed, modules loaded: none.

However,

ssort xs = unfold extractMin xs

works just fine.

I am really confused since I thought that the 2 definitions are equivalent. Any help is appreciated but essentially I would like to understand what the difference between the two definitions is and why was the error thrown in the first place.

samgiz
  • 123
  • 6
  • 3
    For me, the first version works fine as well. But you probably added a signature `[a] -> [a]` to the definition, whereas the signature should be `Ord a => [a] -> [a]` – Willem Van Onsem Nov 09 '17 at 21:22
  • Do you have have a type signature specified for `ssort` in your code? The error message says "relevant bindings" and lists a signature that I don't see defined in your question. – 4castle Nov 09 '17 at 21:28
  • I have not added any type signatures. Those are all of the contents of the file. Besides, even if I did, why would adding an xs change the behaviour – samgiz Nov 09 '17 at 21:35
  • Explicitly stating the type signature of ssort fixed the problem. Still don't understand why the compiler wouldn't infer the type on its own. – samgiz Nov 09 '17 at 22:04
  • 1
    I can reproduce this. About the cause: DMR strikes again. Disabling it via `{-# LANGUAGE NoMonomorphismRestriction #-}` makes the code compile in both ways. – chi Nov 09 '17 at 22:05

0 Answers0