4

次の相互再帰構造を想定します。

type Tree<'a> = 
    | Empty 
    | Node of 'a * 'a Forest
and Forest<'a> = 
    | Nil 
    | Cons of 'a Tree * 'a Forest

目標: この構造の一般的なカタモルフィズムを生成します: foldl、foldr、foldk。

私は次のように素朴なカタモルフィズムを生成しました:

let rec foldTree fEmpty fNode fNil fCons = 
    function 
    | Empty -> fEmpty
    | Node (a, f) -> fNode a (foldForest fEmpty fNode fNil fCons f)
and foldForest fEmpty fNode fNil fCons =
    function
    | Nil -> fNil
    | Cons (t, f') -> fCons (foldTree fEmpty fNode fNil fCons t) (foldForest fEmpty fNode fNil fCons f')

末尾再帰型の foldl (アキュムレータを使用) と末尾再帰型の foldr (継続を使用) を「機械的に」生成するにはどうすればよいですか?

私はScott の Recursive Types and Folds シリーズを読んでいて、再帰構造の折り畳みを「機械的に」生成する方法を理解しています。ただし、再帰的なデータ構造に対して「機械的な」ことを行うためにグーグルで何かを見つけることができません。

PS: インライン化することで上記の相互再帰を取り除くことができますが、tpetricek の Markdown パーサーでの相互再帰の単純化されたバージョンを表すため、そのままにしておきます。

4

1 に答える 1

1

それがあなたが探しているものかどうかはまったくわかりませんが、これはあなたが望むものを与えるようです(一種の)。
重要な点は、型の「内側」にあるものだけを処理し、「外側」にあるものは別のもの (何らかの抽象化) で処理できるようにすることです。

//val foldTree : 'a -> ('b -> 'c -> 'a) -> ('b Forest -> 'c) -> 'b Tree -> 'a
let foldTree fEmpty fNode fForest = function
  Empty       -> fEmpty
| Node (a, f) -> fNode a (fForest f)

// val foldForest : 'a -> ('b -> 'a -> 'a) -> ('c Tree -> 'b) -> 'c Forest -> 'a
let rec foldForest fNil fCons fTree =
  let recurse = foldForest fNil fCons fTree
  function
    Nil         -> fNil
  | Cons (t, f) -> fCons (fTree t) (recurse f)

let foldForestAcc fNil fCons fTree =
  let rec aux acc = function
    Nil         -> acc
  | Cons (t, f) -> aux (fCons (fTree t) acc) f
  aux fNil

let foldForestCont fNil fCons fTree =
  let rec aux cont = function
    Nil         -> cont fNil
  | Cons (t, f) -> aux (fCons (fTree t) >> cont) f
  aux id

求めるものにより適している場合は、次の代替手段もあります。

let fold fEmpty fNode fNil fCons =
  let rec auxT = function
    Empty       -> fEmpty
  | Node (a, f) -> fNode a (auxF f)
  and auxF = function
    Nil         -> fNil
  | Cons (t, f) -> fCons (auxT t) (auxF f)
  auxT

let foldAcc fEmpty fNode fNil fCons =
  let rec auxT acc = function
    Empty       -> acc
  | Node (a, f) -> fNode a (auxF fNil f)
  and auxF acc = function
    Nil         -> acc
  | Cons (t, f) -> auxF (fCons (auxT fEmpty t) acc) f
  auxT fEmpty

let foldCont fEmpty fNode fNil fCons =
  let rec auxT cont = function
    Empty -> cont fEmpty
  | Node (a, f) -> cont (fNode a (auxF id f))
  and auxF cont = function
    Nil -> cont fNil
  | Cons (t, f) -> auxF (cont >> fCons (auxT id t)) f
  auxT id
于 2016-10-26T19:42:10.147 に答える