多态递归-语法和用途? [英] Polymorphic recursion - syntax and uses?

问题描述

我花了很多时间来研究learningyouahaskell，但是我没有找到关于多态递归的很好的解释！

I've spent significant time looking over learnyouahaskell and I haven't found a good explanation of polymorphic recursion!

我了解基本的递归结构:

I understand basic recursive structures:

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

多态递归是什么样的?它的好处/用途是什么?

What would polymorphic recursion look like? And what are its benefits/uses?

推荐答案

多态递归的类型推断是不确定的，这意味着即使类型正确，编译器也无法推断

Type inference for polymorphic recursion is undecidable, meaning the compiler cannot infer the type of such a function even when it is well-typed.

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

For example, an ordinary list applies List to the same (polymorphic) type on both sides:

data List a = Cons a (List a)

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

while this type taken from the Wikipedia article applies Nested to two different (polymorphic) types, a and [a]:

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

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

From the same article, the compiler will fail to infer the type of a relatively straightforward length function

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

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

because length is applied to values of two different types in the second equation, Nested a and Nested [a].

解决方案是断言类型确实是Nested a -> Int.

The solution is to assert that the type is indeed Nested a -> Int.

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

这篇关于多态递归-语法和用途?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！