recursion - 编译器用多态递归函数耗尽内存

Question

如果我尝试编译以下代码以添加到fingertree，elm 编译器会等待很长时间，然后报告内存不足。

module FingerTree exposing(..) 
type Node a
  = Node2 a a
  | Node3 a a a

type Finger a
  = One a
  | Two a a
  | Three a a a
  | Four a a a a

type FingerTree a
  =Empty
  |Single a
  |Deep (Finger a) (FingerTree(Node a)) (Finger a)

fLeftAdd: a -> Finger a -> Finger a
fLeftAdd a0 finger =
  case finger of
    One a1 -> Two a0 a1
    Two a1 a2 -> Three a0 a1 a2
    Three a1 a2 a3 -> Four a0 a1 a2 a3
    Four  a1 a2 a3 a4 -> finger

leftAdd: a -> FingerTree a -> FingerTree a
leftAdd a0 fingerTree=
  case fingerTree of
    Empty -> Single a0
    Single a1 -> Deep (One a0) Empty (One a1)
    Deep left middle right ->
      case left of
        Four a1 a2 a3 a4 ->
          Deep(Two a0 a1) ( leftAdd (Node3 a2 a3 a4) middle) right
        _ -> Deep (fLeftAdd left a0) middle right

我的第一个想法是，也许你不能拥有多态递归(多态函数用不同的类型签名调用自己)。然而，这个变体用列表替换了自定义的“Finger”和“Node”类型，编译得很好:

module HackyTree exposing(..)
type HackyTree a
  = Empty
    |Single a
    |Deep (List a) (HackyTree (List a)) (List a)

leftAdd: a -> HackyTree a -> HackyTree a
leftAdd a0 tree=
   case tree of
    Empty -> Single a0
    Single a1 -> Deep [a0] Empty [a1]
    Deep left middle right ->
      case left of
         [a1, a2, a3, a4] ->
             Deep [a0, a1] ( leftAdd [a2, a3, a4] middle) right
         _ -> Deep (a0::left) middle right

我想让第一个版本正常工作。这是编译器错误吗？有没有推荐的重构方法来避免这种情况？

Answer 1

你确定你的最后一行是 _ -> Deep (fLeftAdd left a0) middle right而不是 _ -> Deep (fLeftAdd a0 left) middle right ?如果我更改它，一切都可以正常编译。

注意fLeftAdd的签名是 fLeftAdd: a -> Finger a -> Finger a .您正在 FingerTree a 上进行模式匹配，尤其是 Deep (Finger a) (FingerTree(Node a)) (Finger a)案件。

与 _ -> Deep (fLeftAdd left a0) middle right您正在申请 fLeftAdd到 left ，这是一个 Finger a并到 a0 ，这是一个 a .
你也有约束 (fLeftAdd left a0) 的结果和 right具有相同的类型。

这意味着 (fLeftAdd left a0)应该产生一个 Finger a当给出 Finger a和一个 a作为参数，从 fLeftAdd: a -> Finger a -> Finger a 开始破坏类型推断.

这是编译器不会耗尽内存的最小示例:

leftAdd: a -> FingerTree a -> FingerTree a
leftAdd a0 fingerTree=
  case fingerTree of
    Deep left middle right ->
      Deep (fLeftAdd left a0) middle right
    _ -> Single a0

我粘贴在 Try Elm我收到以下错误消息:

-- TYPE MISMATCH ---------------------------------------------------------------

The type annotation for leftAdd does not match its definition.

27| leftAdd: a -> FingerTree a -> FingerTree a ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The type annotation is saying:

a -> FingerTree a -> FingerTree a

But I am inferring that the definition has this type:

Finger ? -> FingerTree ? -> FingerTree (Finger ?)

Hint: A type annotation is too generic. You can probably just switch to the type I inferred. These issues can be subtle though, so read more about it. https://github.com/elm-lang/elm-compiler/blob/0.17.0/hints/type-annotations.md

-- INFINITE TYPE ---------------------------------------------------------------

I am inferring a weird self-referential type for left

30| Deep left middle right -> ^^^^ Here is my best effort at writing down the type. You will see ? and ∞ for parts of the type that repeat something already printed out infinitely.

?

Usually staring at the type is not so helpful in these cases, so definitely read the debugging hints for ideas on how to figure this out: https://github.com/elm-lang/elm-compiler/blob/0.17.0/hints/infinite-type.md

我建议您尝试创建一个 simple self contained compilable example并在 compiler project 上提出问题