Haskell - 如何在函数体中使用类型签名中指定的类型参数？

Question

我有以下堆排序代码。

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

这不会编译并出现以下错误 -

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)
   |                            ^^^^^^^^^^^^^^^^^^

我认为这是因为函数体中的 a 与函数签名中的 a 不同。例如，如果我启用部分类型签名并执行

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

代码编译时出现以下警告(但没有错误)。

λ> :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.

那么，我该如何使用部分类型签名功能来完成这项工作呢？通常，如何在函数定义中使用函数签名中的类型参数？

Answer 1

如评论中所述，您可以使用 ScopedTypeVariables 扩展来执行此操作。这允许函数体中使用的类型变量引用函数签名中使用的相同变量，但您必须使用 forall 关键字“选择加入”:

{-# 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)

在这种特殊情况下，您可以通过将 Heap.fromList 或 Heap.toList 专门化为 MinHeap 来完成此操作而无需任何扩展。例如:

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

这里，heapsort' 和 minHeapFromList 的签名中的 a 类型变量是不相关的，但当然，它们在主体中统一对于 heapsort'。