haskell - 多态递归 - 语法和用途？

Question

我花了很多时间查看 learnyouahaskell，但没有找到多态递归的良好解释!

我了解基本的递归结构:

myFunction :: [Int] -> [Int]
myFunction [] = []
myFunction (x : xs) = (\x -> x + 1) x : myFunction xs

多态递归会是什么样子？它的好处/用途是什么？

Answer 1

多态递归的类型推断是不可判定的，这意味着编译器无法推断此类函数的类型，即使它的类型正确。

例如，普通列表将 List 应用于两侧相同(多态)类型:

data List a = Cons a (List a)

而此类型取自 Wikipedia article将Nested应用于两种不同的(多态)类型:a和[a]:

data Nested a = a :<: (Nested [a]) | Epsilon

在同一篇文章中，编译器将无法推断相对简单的 length 函数的类型

length Epsilon = 0
length (a :<: xs) = 1 + length xs

因为length应用于第二个方程中两种不同类型的值，Nested a和Nested [a]。

解决方案是断言该类型确实是嵌套了 -> Int。

length :: Nested a -> Int
length Epsilon = 0
length (a :<: xs) = 1 + length xs