相关疑难解决方法(0)

我正在尝试了解catamorphisms,我已经阅读了维基百科文章以及F#博客上F#主题系列中的第一篇文章.

我理解这是折叠的概括(即,将许多值的结构映射到一个值,包括值列表到另一个列表).我认为折叠列表和折叠树是一个典型的例子.

可以使用LINQ的Aggregate运算符或其他一些更高阶的方法在C#中显示它吗？

假设我有两种数据类型Foo和Bar.Foo有字段x和y.条形图有字段x和z.我希望能够编写一个函数,它将Foo或Bar作为参数,提取x值,对其执行一些计算,然后返回一个新的Foo或Bar,并相应地设置x值.

这是一种方法:

class HasX a where
    getX :: a -> Int
    setX :: a -> Int -> a

data Foo = Foo Int Int deriving Show

instance HasX Foo where
    getX (Foo x _) = x
    setX (Foo _ y) val = Foo val y

getY (Foo _ z) = z
setY (Foo x _) val = Foo x val

data Bar = Bar Int Int deriving Show

instance HasX Bar where
    getX (Bar x _) = x
    setX (Bar …

我对Haskell很新,我正在努力研究如何遍历一棵n-ary树.作为输出,我希望获得Leaf值列表(因为分支没有值),因此对于testtree,这将是:4,5

到目前为止我的定义是:

data Tree a = Leaf a | Branch [Tree a] deriving (Show)

travTree                    :: Tree a -> [a]
travTree (Leaf x)           = [x]
travTree (Branch (x:xs))    = travTree x : travTree xs

testtree = Branch [(Leaf "4"), (Leaf "5")]

但它给出了错误:

Couldn't match expected type `Tree a'
  against inferred type `[Tree a]'
In the first argument of `travTree', namely `xs'
In the second argument of `(:)', namely `travTree xs'
In the expression: travTree x : travTree xs

我假设这是因为xs是一个树列表,它期待一棵奇异的树.有没有办法做到这一点？我一直在尝试地图功能,顺序如下:

travTree …

我觉得理解一个仿函数的固定点的抽象概念,但是,我仍然在努力弄清楚它的确切实现及其在Haskell中的变形.

例如,如果我定义,如根据"程序员类别理论"一书 - 第359页,下面的代数

-- (Int, LiftF e Int -> Int)

data ListF e a = NilF | ConsF e a

lenAlg :: ListF e Int -> Int
lenAlg (ConsF e n) -> n + 1
lenAlg NilF = 0

根据catamorphism的定义,可以将以下函数应用于ListF的固定点,即List,以计算其长度.

cata lenAlg :: [e] -> Int
cata lenAlg = lenAlg . fmap (cata lenAlg) . unFix

我有两个困惑.首先,如何Haskell编译知道名单是THE LISTF的固定点？我从概念上知道它是,但是编译器如何知道,即,如果我们定义另一个列表,那就是与List相同的一切,我打赌编译器不会自动推断出List'也是ListF的固定点,或者它？(我会感到惊讶).

其次,由于cata lenAlg的递归性质,它总是试图取消修复数据构造函数的外层以暴露仿函数的内层(我的解释是否正确？).但是,如果我们已经在叶子上,我们怎么能调用这个函数调用呢？

fmap (cata lenAlg) Nil

举个例子,有人可以帮助为下面的函数调用写一个执行跟踪来澄清吗？

cata lenAlg Cons 1 (Cons 2 Nil)

我可能遗漏了一些显而易见的事情,但是我希望这个问题对于其他有类似困惑的人来说仍然有意义.

回答总结

@nm回答了我的第一个问题,指出为了让Haskell编译器弄清楚Functor A是Functor B的一个固定点,我们需要明确.在这种情况下,它是

type …

这是我fold为树实现(左)的尝试(它是非常简化的版本,但仔细地再现了真正的树结构):

type 'a tree = Leaf of 'a | Node of 'a * 'a tree list

let rec fold t acc f =
  match t with
  | Leaf x -> f acc x None
  | Node (x, lst) ->
    let deferred acc =
      List.fold_left (fun acc t' -> fold t' acc f) acc lst in
    f acc x (Some deferred)

我们的想法是使用延迟调用子树.它让我们:

• 如果需要,跳过子树遍历
• 初始化子树遍历并撰写结果

玩具示例:

open Printf

let () =
  let tree = Node (3, [Leaf 5; Leaf 3; …

目前,梦想还在继续,在每个haskell概念中我都知道我更有吸引力.然而,我还没有完全实现这个珍贵的@ luqui对我之前关于catamorphism的问题的回答,我会回来直到它没问题.这是关于维基百科上的这个示例代码,处理BINARY树上的catamorphism.

尽管如此,我曾尝试推行了catamorphism 非二进制树,但我面对一些麻烦:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a ?  r
                                                 , composite :: [r] ?  r }

foldComposition :: CompositionAlgebra a r ?  Composition a ?  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- 最新的一行不会请"g [y]"

maxOfPair :: a ?  a …