F#
フォールド

折りたたみの紹介、いくつかの例

フォールドは、要素のシーケンスとともに使用される（高次の）関数です。彼らはseq<'a>を'b seq<'a>崩壊させseq<'a>ここで'bは任意の型です（おそらくまだ'a ）。これは少し抽象的なので、具体的な実用的な例を得ることができます。

すべての数値の合計を計算する

この例では、 'aはintです。私たちは数字のリストを持っていて、それをすべて集計して計算します。リストの数を合計するには[1; 2; 3]書きます

List.fold (fun x y -> x + y) 0 [1; 2; 3] // val it : int = 6

リストを扱っているのでListモジュール、つまりList.fold foldを使います。最初の引数foldは、バイナリ関数のフォルダです。 2番目の引数は初期値です。 foldは、初期値と最初の要素で始まるリスト内の要素にフォルダ関数を連続的に適用することによって、リストを折りたたみ始めます。リストが空の場合、inital値が返されます。

実行例の概要は次のようになります。

let add x y = x + y // this is our folder (a binary function, takes two arguments)
List.fold add 0 [1; 2; 3;]
=> List.fold add (add 0 1) [2; 3] 
// the binary function is passed again as the folder in the first argument
// the initial value is updated to add 0 1 = 1 in the second argument
// the tail of the list (all elements except the first one) is passed in the third argument
// it becomes this:
List.fold add 1 [2; 3]
// Repeat untill the list is empty -> then return the "inital" value
List.fold add (add 1 2) [3]
List.fold add 3 [3] // add 1 2 = 3
List.fold add (add 3 3) [] 
List.fold add 6 [] // the list is empty now -> return 6
6

List.sum関数は大まかにList.fold add LanguagePrimitives.GenericZeroここで、汎用ゼロは整数、浮動小数点数、大きな整数などと互換性があります。

リスト内のelemetsをcount （ count実装する）

これは上記とほとんど同じですが、リストの要素の実際の値を無視して、代わりに1を加えます。

List.fold (fun x y -> x + 1) 0 [1; 2; 3] // val it : int = 3

これは次のようにすることもできます：

[1; 2; 3]
|> List.map (fun x -> 1) // turn every elemet into 1, [1; 2; 3] becomes [1; 1; 1]
|> List.sum // sum [1; 1; 1] is 3

したがって、次のようにcountを定義できます。

let count xs = 
    xs 
    |> List.map (fun x -> 1) 
    |> List.fold (+) 0 // or List.sum

リストの最大値を見つける

今回は使用しますList.reduceのようなものですList.foldが、我々はタイプが我々がcompairingされている値であるかわからない、この場合のように初期値なしを：

let max x y = if x > y then x else y
// val max : x:'a -> y: 'a -> 'a when 'a : comparison, so only for types that we can compare
List.reduce max [1; 2; 3; 4; 5] // 5
List.reduce max ["a"; "b"; "c"] // "c", because "c" > "b" > "a"
List.reduce max [true; false] // true, because true > false 

リストの最小値を求める

最大値を見つけるときと同じように、フォルダは異なります

let min x y = if x < y then x else y
List.reduce min [1; 2; 3; 4; 5] // 1
List.reduce min ["a"; "b"; "c"] // "a"
List.reduce min [true; false] // false

リストを連結する

ここではリストのリストを取ります。フォルダ関数は@演算子です

// [1;2] @ [3; 4] = [1; 2; 3; 4]
let merge xs ys = xs @ ys
List.fold merge [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]

あるいは、バイナリ演算子をフォルダ関数として使うこともできます：

List.fold (@) [] [[1;2;3]; [4;5;6]; [7;8;9]] // [1;2;3;4;5;6;7;8;9]
List.fold (+) 0 [1; 2; 3] // 6
List.fold (||) false [true; false] // true, more on this below
List.fold (&&) true [true; false] // false, more on this below
// etc...

数の階乗を計算する

数字を合計するときと同じ考えですが、今ではそれらを乗算します。 nの階乗が必要な場合は、リスト[1 .. n]すべての要素を乗算します。コード：

// the folder
let times x y = x * y
let factorial n = List.fold times 1 [1 .. n]
// Or maybe for big integers
let factorial n = List.fold times 1I [1I .. n] 

forall 、 exists 、 contains実装していcontains

forall allは、シーケンス内のすべての要素が条件を満たすかどうかをチェックします。 exists 、リスト内の少なくとも1つの要素が条件を満たしている場合チェックを。まず、 bool値のリストを折りたたむ方法を知る必要があります。さて、私たちは折り畳みを使用します！ブール演算子は私たちのフォルダ関数になります。

リスト内のすべての要素がtrueであるかどうかを調べるには、 &&関数をtrueて初期値として崩壊させます。

List.fold (&&) true [true; true; true] // true
List.fold (&&) true [] // true, empty list -> return inital value
List.fold (&&) true [false; true] // false

同様に、ある要素がリストブール値でtrueであるかどうかをチェックするために、 ||初期値としてfalseを持つ演算子：

List.fold (||) false [true; false] // true
List.fold (||) false [false; false] // false, all are false, no element is true
List.fold (||) false [] // false, empty list -> return inital value

forall戻り、 existsます。ここでは任意のタイプのリストを取り、条件を使用してすべての要素をブール値に変換し、次にそれを折りたたむ。

let forall condition elements = 
    elements 
    |> List.map condition // condition : 'a -> bool
    |> List.fold (&&) true

let exists condition elements = 
    elements
    |> List.map condition
    |> List.fold (||) false

[1; 2; 3; 4]が5：

forall (fun n -> n < 5) [1 .. 4] // true

exists使ってcontainsメソッドを定義exists ：

let contains x xs = exists (fun y -> y = x) xs

あるいは

let contains x xs = exists ((=) x) xs

次に、リスト[1. .. 5]に値2が含まれているかどうか確認します。

contains 2 [1..5] // true

reverse実装：

let reverse xs = List.fold (fun acc x -> x :: acc) [] xs
reverse [1 .. 5] // [5; 4; 3; 2; 1]

mapとfilter実装

let map f = List.fold (fun acc x -> List.append acc [f x]) List.empty
// map (fun x -> x * x) [1..5] -> [1; 4; 9; 16; 25]   

let filter p = Seq.fold (fun acc x -> seq { yield! acc; if p(x) then yield x }) Seq.empty
// filter (fun x -> x % 2 = 0) [1..10] -> [2; 4; 6; 8; 10]

foldができないものはありますか？私は本当に知っていない

リストのすべての要素の合計を計算する

数値リストの（float型、int型、または大きな整数型の）項の和を計算するには、List.sumを使用することをお勧めします。List.foldは、そのような合計を計算するのに最適な関数です。

1. 複素数の和

この例では、複素数のリストを宣言し、リスト内のすべての項の合計を計算します。

プログラムの冒頭で、System.Numericsへの参照を追加します

開いているSystem.Numerics

合計を計算するために、アキュムレータを複素数0に初期化します。

let clist = [new Complex(1.0, 52.0); new Complex(2.0, -2.0); new Complex(0.0, 1.0)]

let sum = List.fold (+) (new Complex(0.0, 0.0)) clist

結果：

(3, 51)

2. ユニオン型の数の和

リストが複数の共用体（float型またはint型）で構成され、これらの数の合計を計算したいとします。

次の数値型の前に宣言します。

type number = 
| Float of float
| Int of int

リストのタイプ番号の合計を計算する：

let list = [Float(1.3); Int(2); Float(10.2)]

let sum = List.fold (
                         fun acc elem -> 
                                        match elem with
                                        | Float(elem) -> acc + elem
                                        | Int(elem) -> acc + float(elem)
                        ) 0.0 list

結果：

13.5

アキュムレータを表す関数の最初のパラメータはfloat型で、リスト内の項目を表す2番目のパラメータはnumber型です。しかし、追加する前に、elemがInt型である場合にfloat型にパターンマッチングとキャストを使用する必要があります。