Lazy を使って Seq の foldBack 的なものを書いてみた

@yoshihiro503 Seq.foldBack は標準にはないですが、仮にあったとして、たとえば Haskell のように、map を foldr で実装する的なことってできないんじゃ、と思ってるんですが、どんなもんでしょうか？

2012-01-20 00:30:23 via web to @yoshihiro503

書いてみた。

let rec foldBack f xs init =
  if xs |> Seq.isEmpty then init
  else f (Seq.head xs)(lazy foldBack f (Seq.skip 1 xs) init)

let cons x (xs: Lazy<'a seq>) = seq { yield x; yield! xs.Force() }

let map f xs = foldBack (f >> cons) xs Seq.empty

foldBack のシグネチャに Lazy が表れてしまってううむ・・・まぁしゃーなし。
んで、

let xs = Seq.initInfinite id

printfn "%A" (xs |> map (( * )2) |> Seq.take 10)
(*
seq [0; 2; 4; 6; ...]
*)

infinite な Seq が扱えた！
副作用ありにしてもうちょっと面白い例。

let xs =
  Seq.initInfinite id
  |> map (fun a -> printfn "%d" a; a * 2)

printfn "%A" (xs |> Seq.take 2)
printfn "===="
printfn "%A" (xs |> Seq.take 10 |> Seq.toList)
(*
0
1
seq [0; 2]
====
2
3
4
5
6
7
8
9
[0; 2; 4; 6; 8; 10; 12; 14; 16; 18]
*)

各要素ごとに一回しか map に渡した関数が呼び出されていない！

アクティブパターンを定義すると、

let (|EmptySeq|Cons|) xs =
  if xs |> Seq.isEmpty then EmptySeq
  else Cons ((Seq.head xs), (Seq.skip 1 xs))

let rec foldBack f xs init =
  match xs with
  | EmptySeq -> init
  | Cons(x, xs) -> f x (lazy foldBack f xs init)

let cons x (xs: Lazy<'a seq>) = seq { yield x; yield! xs.Force() }

let map f xs = foldBack (f >> cons) xs Seq.empty

すっきり！