Реализация карты на дереве с помощью сгиба

Question

Я пытаюсь реализовать карту, используя складку. Я мог бы сделать это в Haskell

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) 


foldTree :: Tree a -> b -> (b -> a -> b -> b) -> b 
foldTree EmptyTree d _ = d 
foldTree (Node a l r) d f = f (foldTree l d f) a (foldTree r d f) 


mapTree :: Tree a -> (a -> b) -> Tree b 
mapTree tree f = foldTree tree EmptyTree (\l n r -> Node (f n) l r) 

Однако, когда я попытался портирование на Scala, я немного застрял

sealed trait Tree[+A] 
case object EmptyTree extends Tree[Nothing] 
case class Node[A](value: A , left: Tree[A], right: Tree[A]) extends Tree[A] 


def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B) : B = t match { 
    case EmptyTree => z 
    case Node(x,l,r) => f (fold(l , z)(f) , x , fold(r , z)(f)) 
    } 

    def map(tree:Tree[Int])(f:Int=>Int) : Tree[Int] = fold(tree , EmptyTree)((l,x,r) => Node(f(x),l,r)) 

Компилятор жалуется, что он ожидает EmptyTree в функции я прохожу свернуть ,

fold(tree , EmptyTree)((l,x,r) => Node(f(x),l,r)) 

Тип возврата для Карты - это дерево, поэтому я ожидал, что это сработает. Какие-либо предложения ?

Answer 1

Попробуйте написать последнюю строку в

def map(tree:Tree[Int])(f:Int=>Int) : Tree[Int] = fold(tree , EmptyTree:Tree[Int])((l,x,r) => Node(f(x),l,r)) 

умозаключение типа Scala, очень ограничены по сравнению с Haskell, в этом случае он пытается infere тип fold от его аргументов слева направо, и incorectly решает, что результат тип складки должен быть EmptyTree, а не Tree[Int]. Обычно добавление конструктора вспомогательной компаньона объекта родительского типа помогает в этой ситуации немного, например, в объекте Option есть конструктор

def empty[A]: Option[A] 

который возвращает родительский тип.

Answer 2

В качестве альтернативы решению @ виталий, делают параметры типа для fold явного:

def map(tree: Tree[Int])(f: Int=>Int): Tree[Int] = 
    fold[Int, Tree[Int]](tree, EmptyTree)((l, x, r) => Node[Int](f(x), l, r)) 
    // ^^^^^^^^^^^^^^