F#
Складки

Введение в складки, с несколькими примерами

Складки - это функции (более высокого порядка), используемые с последовательностями элементов. Они сворачивают seq<'a> в 'b где 'b - любой тип (возможно, еще 'a ). Это немного абстрактно, поэтому давайте рассмотрим конкретные практические примеры.

Вычисление суммы всех чисел

В этом примере 'a является int . У нас есть список чисел, и мы хотим рассчитать сумму всех его чисел. Суммировать номера списка [1; 2; 3] пишем

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

Позвольте мне объяснить, потому что мы имеем дело со списками, мы используем fold в модуле List , следовательно List.fold . первый аргумент fold принимает двоичную функцию - папку . Второй аргумент - это начальное значение . fold начинает складывать список, последовательно применяя функцию папки к элементам в списке, начиная с начального значения и первого элемента. Если список пуст, возвращается исходное значение!

Схематический пример примера выполнения выглядит так:

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 где общий ноль делает его совместимым с целыми числами, поплавками, большими целыми числами и т. Д.

Подсчет элементов в списке ( 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 но без начального значения, как в этом случае, когда мы не знаем, что тип имеет значения, которые мы компилируем:

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 

Поиск минимума списка

Точно так же, как при поиске max, папка отличается

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

функция forall проверяет, удовлетворяют ли все элементы в последовательности условию. exists проверка, если по крайней мере один элемент в списке удовлетворяет условию. Сначала нам нужно знать, как свернуть список значений 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

определить метод contains with 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. Сумма чисел типа объединения

Предположим, что список состоит из чисел union (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, а второй параметр, который представляет элемент в списке, имеет номер типа. Но перед тем, как мы добавим, нам нужно использовать сопоставление образцов и приведение к типу float, когда elem имеет тип Int.