如何在Haskell中压缩玫瑰树

Question

对于Haskell Tic Tac Toe游戏,我试图压缩两棵玫瑰树.我把玫瑰树定义为

data Rose a = a :> [Rose a]

我尝试过以下方法:

zipTrees :: Rose Board -> Rose Int -> Rose (Board, Int)
zipTrees (b :> []) (i :> []) = (b,i) :> []
zipTrees (b :> chib) (i :> chii) = (b, i) :> zipTrees chib chii

但出现错误,因为它可能不符合预期的类型Rose Int,并Rose Board与[Rose Int]和[Rose Board]分别.我对如何以任何其他方式压缩树木一无所知.

为了进一步说明,如果我想拉树

a :> [a :> [a :> []], a :> []]

而且b :> [b :> [b :> []], b :> []],我想要归还树

(a, b) :> [(a, b) :> [(a, b) :> []], (a,b) :> []]

Answer 1

chib并且chii是树木的列表,而不是树木本身.你不能只是打电话zipTrees给他们.你需要递减

zipTrees :: Rose Board -> Rose Int -> Rose (Board, Int)
zipTrees (b :> [])       (i :> _)        = …
zipTrees (b :> _)        (i :> [])       = …
zipTrees (b :> (cb:cbs)) (i :> (ci:cis)) = …

或者只是使用 zipWith

zipTrees :: Rose Board -> Rose Int -> Rose (Board, Int)
zipTrees (b :> chib) (i :> chii) = (b, i) :> zipWith zipTrees chib chii
--                                           ^^^^^^^