CODEWITHSUNDEEP
haskell
Kakaji
Kakaji

Reputation: 1491

Haskell - How to use a type-parameter specified in type-signature in the function body?

I have the following heapsort code. 

heapsort :: (Ord a) => [a] -> [a]
heapsort xs = Heap.toList (Heap.fromList $ xs :: Heap.MinHeap a)

This does not compile with the following error - 

mergeLists.hs:32:28: error:
    • Couldn't match type ‘a1’ with ‘a’
      ‘a1’ is a rigid type variable bound by
        an expression type signature:
          forall a1. Heap.MinHeap a1
        at mergeLists.hs:32:50-63
      ‘a’ is a rigid type variable bound by
        the type signature for:
          heapsort :: forall a. Ord a => [a] -> [a]
        at mergeLists.hs:31:1-33
      Expected type: Heap.MinHeap a1
        Actual type: Heap.Heap Heap.MinPolicy a
    • In the first argument of ‘Heap.toList’, namely
        ‘(Heap.fromList $ xs :: Heap.MinHeap a)’
      In the expression:
        Heap.toList (Heap.fromList $ xs :: Heap.MinHeap a)
      In an equation for ‘heapsort’:
          heapsort xs = Heap.toList (Heap.fromList $ xs :: Heap.MinHeap a)
    • Relevant bindings include
        xs :: [a] (bound at mergeLists.hs:32:10)
        heapsort :: [a] -> [a] (bound at mergeLists.hs:32:1)
   |
32 | heapsort xs = Heap.toList (Heap.fromList $ xs :: Heap.MinHeap a)
   |                            ^^^^^^^^^^^^^^^^^^

I think this is because a in function body is not the same as a in the signature of the function. For example, if I enable partial type signatures and do

heapsort :: (Ord a) => [a] -> [a]
heapsort xs = Heap.toList (Heap.fromList $ xs :: Heap.MinHeap _)

the code compiles with the following warning (but no error).

λ> :load mergeLists
[1 of 1] Compiling Main             ( mergeLists.hs, interpreted )

mergeLists.hs:32:63: warning: [-Wpartial-type-signatures]
    • Found type wildcard ‘_’ standing for ‘a’
      Where: ‘a’ is a rigid type variable bound by
               the type signature for:
                 heapsort :: forall a. Ord a => [a] -> [a]
               at mergeLists.hs:31:1-33
    • In an expression type signature: Heap.MinHeap _
      In the first argument of ‘Heap.toList’, namely
        ‘(Heap.fromList $ xs :: Heap.MinHeap _)’
      In the expression:
        Heap.toList (Heap.fromList $ xs :: Heap.MinHeap _)
    • Relevant bindings include
        xs :: [a] (bound at mergeLists.hs:32:10)
        heapsort :: [a] -> [a] (bound at mergeLists.hs:32:1)
   |
32 | heapsort xs = Heap.toList (Heap.fromList $ xs :: Heap.MinHeap _)
   |                                                               ^
Ok, one module loaded.

So, how do I make this work with using partial type signatures feature? In general, how do I use a type-parameter from function's signature in the function's definition?

Upvotes: 3

Views: 287

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 51159

As indicated in the comments, you can do this using the ScopedTypeVariables extension. This allows type variables used in function bodies to refer to the same variables used in the functions' signatures, but you have to "opt in" using the forall keyword:

{-# LANGUAGE ScopedTypeVariables #-}

import qualified Data.Heap as Heap

heapsort :: forall a . (Ord a) => [a] -> [a]
heapsort xs = Heap.toList (Heap.fromList xs :: Heap.MinHeap a)

In this particular case, you could do it without any extension by specializing either Heap.fromList or Heap.toList to MinHeap. For example:

heapsort' :: (Ord a) => [a] -> [a]
heapsort' = Heap.toList . minHeapFromList
  where minHeapFromList :: (Ord a) => [a] -> Heap.MinHeap a
        minHeapFromList = Heap.fromList

Here, the a type variables in the signatures for heapsort' and minHeapFromList are unrelated but, of course, they unify in the body for heapsort'.

Upvotes: 4

Related Questions