F#メモ

プログラミングF#のメモ

• 末尾再帰

元の関数

let factorial x = 
    let rec tailFactorial x acc =
        if x <= 1 then acc
        else tailFactorial (x-1) (acc * x)
    tailFactorial x 1

ルイパンコ結果

public static class Factorial
{
	//
	// Static Methods
	//
	public static int factorial (int x)
	{
		return Factorial.tailFactorial@5 (x, 1);
	}

	internal static int tailFactorial@5 (int x, int acc)
	{
		while (x > 1) {
			int arg_0E_0 = x - 1;
			acc *= x;
			x = arg_0E_0;
		}
		return acc;
	}
}

ほぼ例と同じですね。
末尾再帰がwhileに置き換えられています。

• 継続

つまり、スタック上に「残されているもの」を格納するのではなく、「残されていること」を関数として格納してしまうわけです。

？？？

スタック領域（再帰呼び出し）の代わりにヒープ領域（関数値）を使用するのです。

…？

なんて思いつつうんうん唸って
http://www.geocities.jp/m_hiroi/func/haskell38.html
のfib(n)辺りまで読んでなんとなく分かった気がした。

二分木の葉の数を求める関数を継続で。
本に載っていたのと同じようなスタイルでやってみる。

type BinTree<'T> =
    | Node of 'T * BinTree<'T> * BinTree<'T>
    | Empty

type IStep<'T> =
    | Fin of int
    | Step of int * (int -> IStep<'T>)

let count (tree : BinTree<'T>) =
    let rec cnt tree acc =
        match tree with
        | Empty -> acc(0)
        | Node (x, l, r) ->
            Step(1, fun a -> cnt l (fun b -> cnt r (fun c -> (acc (a + b + c)))))

    let steps = cnt tree (fun x -> Fin(x))

    let rec proc step =
        match step with
        | Fin(s) -> s
        | Step(x, next) -> proc (next (x))

    proc steps

ポイントは

Step(1, fun a -> cnt l (fun b -> cnt r (fun c -> (acc (a + b + c)))))

の部分？
1が自分自信の葉っぱの数
fun a -> cnt l ...
のaが左側の葉っぱの和
fun b -> cnt r ...
のbが右側の葉っぱの和
fun d -> ...
でdが今までの総和にそれぞれの和を加算

let tree = Node(1, Node(2, Node(3, Node(4, Node(5, Empty, Empty), Node(6, Empty, Empty)), Node(7, Empty, Empty)), Empty), Empty)

count tree
> val it : int = 7
count Empty
val it : int = 0
count (Node(1, Node(2, Empty, Empty), Node(3, Empty, Empty)))
val it : int = 3

最後のを展開して確認。
展開順はだいぶ適当で省略する。

count (Node(1, Node(2, Empty, Empty), Node(3, Empty, Empty)))

cnt tree (fun x -> Fin(x)) (Node(1, Node(2, Empty, Empty), Node(3, Empty, Empty)))
→ Step(1, fun a -> cnt Node(2, Empty, Empty (fun b -> cnt Node(3, Empty, Empty (fun c -> (acc (a + b + c)))))
→ Step(1, Step(1, Step(1, fun c -> a + b + c))
→ 3

頭に？？？浮かべている状況からは多少前進した気がする。

おまけのルイパンコ結果。
だいぶ長かったの関係ありそうな部分だけで属性とか色々削除。

public static class TreeCount
{
	internal static TreeCount.IStep<b> cnt@12<a, b> (TreeCount.BinTree<a> tree, FSharpFunc<int, TreeCount.IStep<b>> acc)
	{
		if (tree is TreeCount.BinTree<a>.Node) {
			TreeCount.BinTree<a>.Node node = (TreeCount.BinTree<a>.Node)tree;
			TreeCount.BinTree<a> item = node.item3;
			TreeCount.BinTree<a> item2 = node.item2;
			return TreeCount.IStep<b>.NewStep (1, new TreeCount<b, a>.cnt@16-1 (acc, item, item2));
		}
		return acc.Invoke (0);
	}

	public static int count<T> (TreeCount.BinTree<T> tree)
	{
		TreeCount.IStep<object> step = TreeCount.cnt@12<T, object> (tree, new TreeCount.steps@18 ());
		return TreeCount.proc@20<object> (step);
	}

	internal static int proc@20<a> (TreeCount.IStep<a> step)
	{
		while (step is TreeCount.IStep<a>.Step) {
			TreeCount.IStep<a>.Step step2 = (TreeCount.IStep<a>.Step)step;
			int item = step2.item1;
			FSharpFunc<int, TreeCount.IStep<a>> item2 = step2.item2;
			step = item2.Invoke (item);
		}
		return ((TreeCount.IStep<a>.Fin)step).item;
	}

	//
	// Nested Types
	//
	public abstract class BinTree<T> : IEquatable<TreeCount.BinTree<T>>, IStructuralEquatable, IComparable<TreeCount.BinTree<T>>, IComparable, IStructuralComparable
	{
		public static class Tags
		{
			public const int Node = 0;

			public const int Empty = 1;
		}

		public class Node : TreeCount.BinTree<T>
		{
			[CompilationMapping (SourceConstructFlags.Field, 0, 0), DebuggerNonUserCode, CompilerGenerated]
			public T Item1 {
				[DebuggerNonUserCode, CompilerGenerated]
				get {
					return this.item1;
				}
			}

			public TreeCount.BinTree<T> Item2 {
				[DebuggerNonUserCode, CompilerGenerated]
				get {
					return this.item2;
				}
			}

			public TreeCount.BinTree<T> Item3 {
				[DebuggerNonUserCode, CompilerGenerated]
				get {
					return this.item3;
				}
			}

			internal Node (T item1, TreeCount.BinTree<T> item2, TreeCount.BinTree<T> item3)
			{
				this.item1 = item1;
				this.item2 = item2;
				this.item3 = item3;
			}
		}

		internal class _Empty : TreeCount.BinTree<T>
		{
			[DebuggerNonUserCode, CompilerGenerated]
			internal _Empty ()
			{
			}
		}

		internal class Node@DebugTypeProxy
		{
			public T Item1 {
				[DebuggerNonUserCode, CompilerGenerated]
				get {
					return this._obj.item1;
				}
			}

			public TreeCount.BinTree<T> Item2 {
				[DebuggerNonUserCode, CompilerGenerated]
				get {
					return this._obj.item2;
				}
			}

			public TreeCount.BinTree<T> Item3 {
				[DebuggerNonUserCode, CompilerGenerated]
				get {
					return this._obj.item3;
				}
			}

			public Node@DebugTypeProxy (TreeCount.BinTree<T>.Node obj)
			{
				this._obj = obj;
			}
		}

		public int Tag {
			get {
				return (!(this is TreeCount.BinTree<T>._Empty)) ? 0 : 1;
			}
		}

		public bool IsNode {
			get {
				return this is TreeCount.BinTree<T>.Node;
			}
		}

		public static TreeCount.BinTree<T> Empty {
			get {
				return TreeCount.BinTree<T>._unique_Empty;
			}
		}

		public bool IsEmpty {
			get {
				return this is TreeCount.BinTree<T>._Empty;
			}
		}

		static BinTree ()
		{
			// Note: this type is marked as 'beforefieldinit'.
			TreeCount.BinTree<T>._unique_Empty = new TreeCount.BinTree<T>._Empty ();
		}

		internal BinTree ()
		{
		}

		public static TreeCount.BinTree<T> NewNode (T item1, TreeCount.BinTree<T> item2, TreeCount.BinTree<T> item3)
		{
			return new TreeCount.BinTree<T>.Node (item1, item2, item3);
		}
	}

	internal class cnt@16-1<b, a> : FSharpFunc<int, TreeCount.IStep<b>>
	{
		public FSharpFunc<int, TreeCount.IStep<b>> acc;

		public TreeCount.BinTree<a> r;

		public TreeCount.BinTree<a> l;

		internal cnt@16-1 (FSharpFunc<int, TreeCount.IStep<b>> acc, TreeCount.BinTree<a> r, TreeCount.BinTree<a> l)
		{
			this.acc = acc;
			this.r = r;
			this.l = l;
		}

		public override TreeCount.IStep<b> Invoke (int a)
		{
			return TreeCount.cnt@12<a, b> (this.l, new TreeCount<b, a>.cnt@16-2 (this.acc, this.r, a));
		}
	}

	internal class cnt@16-2<b, a> : FSharpFunc<int, TreeCount.IStep<b>>
	{
		public FSharpFunc<int, TreeCount.IStep<b>> acc;

		public TreeCount.BinTree<a> r;

		public int a;

		internal cnt@16-2 (FSharpFunc<int, TreeCount.IStep<b>> acc, TreeCount.BinTree<a> r, int a)
		{
			this.acc = acc;
			this.r = r;
			this.a = a;
		}

		public override TreeCount.IStep<b> Invoke (int b)
		{
			return TreeCount.cnt@12<a, b> (this.r, new TreeCount<b>.cnt@16-3 (this.acc, this.a, b));
		}
	}

	internal class cnt@16-3<b> : FSharpFunc<int, TreeCount.IStep<b>>
	{
		public FSharpFunc<int, TreeCount.IStep<b>> acc;

		public int a;

		public int b;

		internal cnt@16-3 (FSharpFunc<int, TreeCount.IStep<b>> acc, int a, int b)
		{
			this.acc = acc;
			this.a = a;
			this.b = b;
		}

		public override TreeCount.IStep<b> Invoke (int d)
		{
			return this.acc.Invoke (d + this.a + this.b);
		}
	}

	public abstract class IStep<T>
	{
		public static class Tags
		{
			public const int Fin = 0;

			public const int Step = 1;
		}

		public class Fin : TreeCount.IStep<T>
		{
			public int Item {
				get {
					return this.item;
				}
			}

			internal Fin (int item)
			{
				this.item = item;
			}
		}

		public class Step : TreeCount.IStep<T>
		{
			public int Item1 {
				get {
					return this.item1;
				}
			}

			public FSharpFunc<int, TreeCount.IStep<T>> Item2 {
				get {
					return this.item2;
				}
			}

			internal Step (int item1, FSharpFunc<int, TreeCount.IStep<T>> item2)
			{
				this.item1 = item1;
				this.item2 = item2;
			}
		}

		public int Tag {
			get {
				return (!(this is TreeCount.IStep<T>.Step)) ? 0 : 1;
			}
		}

		public bool IsFin {
			get {
				return this is TreeCount.IStep<T>.Fin;
			}
		}

		public bool IsStep {
			get {
				return this is TreeCount.IStep<T>.Step;
			}
		}

		internal IStep ()
		{
		}

		public static TreeCount.IStep<T> NewFin (int item)
		{
			return new TreeCount.IStep<T>.Fin (item);
		}

		public static TreeCount.IStep<T> NewStep (int item1, FSharpFunc<int, TreeCount.IStep<T>> item2)
		{
			return new TreeCount.IStep<T>.Step (item1, item2);
		}
	}

	internal class steps@18 : FSharpFunc<int, TreeCount.IStep<object>>
	{
		internal steps@18 ()
		{
		}

		public override TreeCount.IStep<object> Invoke (int x)
		{
			return TreeCount.IStep<object>.NewFin (x);
		}
	}
}