элементы суммирования из определенного пользователем типа данных

Question

Изучив предопределенные типы данных в f # (то есть списках) и суммируя элементы списка или последовательности, я пытаюсь узнать, как я могу работать с пользовательскими типами данных. Скажем, я создаю тип данных, назовите его list1:

type list1 = 
    A
  | B of int * list1

Где:

• A обозначает пустой список
• B создает новый список, добавляя int перед другим списком

, поэтому 1,2,3,4, будут представлены значением list1:

B(1, B(2, B(3, B(4, A))))

Из викибука я узнал, что с помощью списка я могу суммировать элементы, выполнив:

let List.sum [1; 2; 3; 4]

Но как мне суммировать элементы определенного пользователем типа данных? Любые советы будут с благодарностью.

Редактировать: я могу воспользоваться оператором матча:

let rec sumit (l: ilist) : int = 
  match l with
  | (B(x1, A)) -> x1
  | (B(x1, B(x2, A))) -> (x1+x2)

sumit (B(3, B(4, A)))

Я получаю:

val it : int = 7

Как я могу сделать так, чтобы, если у меня было больше 2-х, оно по-прежнему суммировало элементы (то есть (B (3, B (4, B (5, A)))) получало 12?

Answer 1

Помимо хвостовой рекурсии, общее программирование может быть важной концепцией для обучающегося. Зачем заниматься созданием пользовательского типа данных, если он может содержать только целочисленные значения?

Сумма всех элементов списка может быть обобщена как повторное применение оператора сложения ко всем элементам списка и аккумулятора, заполненного начальным состоянием. Это можно обобщить как функциональную складку:

type 'a list1 = A | B of 'a * 'a list1
let fold folder (state : 'State) list =
    let rec loop s = function
    | A -> s
    | B(x : 'T, xs) -> loop (folder s x) xs
    loop state list 
// val fold :
//   folder:('State -> 'T -> 'State) -> state:'State -> list:'T list1 -> 'State
B(1, B(2, B(3, B(4, A))))
|> fold (+) 0
// val it : int = 10

Для создания общей функции sum требуется немного черной магии, называемой статически разрешенными параметрами типа. Сигнатура не красивая, она, по сути, говорит вам, что она ожидает, что оператор (+) для типа успешно скомпилируется.

let inline sum xs = fold (+) Unchecked.defaultof<_> xs
// val inline sum :
//   xs: ^a list1 ->  ^b
//     when ( ^b or  ^a) : (static member ( + ) :  ^b *  ^a ->  ^b)
B(1, B(2, B(3, B(4, A))))
|> sum
// val it : int = 10

Answer 2

Один хороший общий подход к таким вопросам состоит в том, чтобы выписать ваш алгоритм в форме слова или псевдокода, а затем, как только вы выясните свой алгоритм, преобразуйте его в F #. В этом случае, когда вы хотите суммировать списки, это будет выглядеть так:

Первым шагом в выяснении алгоритма является тщательное определение спецификаций проблемы. Я хочу, чтобы алгоритм суммировал мой пользовательский тип списка. Что точно это значит? Или, чтобы быть более конкретным, что именно это означает для двух различных типов значений (A и B), которые могут иметь мой тип настраиваемого списка? Что ж, давайте посмотрим на них по одному. Если список имеет тип A, то это представляет пустой список, поэтому мне нужно решить, какой должна быть сумма пустого списка. Наиболее разумным значением для суммы пустого списка является 0, поэтому правило гласит: «Если список имеет тип A, то сумма равна 0». Теперь, если список имеет тип B, то что означает сумма этого списка? Ну, сумма списка типа B будет его значением int плюс сумма подсписка.

Итак, теперь у нас есть правило "суммы" для каждого из двух типов, которые может иметь list1. Если A, сумма равна 0. Если B, сумма равна (значение + сумма подсписка). И это правило переводит почти дословно в код F #!

let rec sum (lst : list1) =
    match lst with
    | A -> 0
    | B (value, sublist) -> value + sum sublist

Несколько вещей, которые я хочу отметить об этом коде. Во-первых, одна вещь, которую вы могли или не могли видеть раньше (поскольку вы, кажется, начинающий F #), это ключевое слово rec. Это необходимо, когда вы пишете рекурсивную функцию: из-за внутренних деталей того, как реализован синтаксический анализатор F #, если функция собирается вызывать себя, вы должны объявить это заранее, когда вы объявляете имя и параметры функции. Во-вторых, это не лучший способ написания sum функции, потому что она на самом деле не является хвостовой рекурсивной, что означает, что она может вызвать исключение StackOverflowException, если вы попытаетесь суммировать действительно действительно длинный список. На этом этапе изучения F # вам, возможно, пока не стоит беспокоиться об этом, но в конечном итоге вы освоите полезную технику для превращения не хвостовой рекурсивной функции в хвостовую рекурсивную. Он включает в себя добавление дополнительного параметра, обычно называемого «аккумулятор» (и иногда пишется acc для краткости), и правильно рекурсивная версия вышеуказанной функции sum выглядела бы так:

let sum (lst : list1) =
    let rec tailRecursiveSum (acc : int) (lst : list1) =
        match lst with
        | A -> acc
        | B (value, sublist) -> tailRecursiveSum (acc + value) sublist
    tailRecursiveSum 0 lst

Если вы уже в точке, где вы можете это понять, прекрасно! Если вы еще не достигли этой точки, добавьте этот ответ в закладки и вернитесь к нему, как только вы изучите хвостовую рекурсию, потому что эта техника (превращение не хвостовой рекурсивной функции в хвостовую рекурсивную с использованием внутренней функция и параметр аккумулятора) - очень ценный инструмент, имеющий множество приложений в программировании на F #.