Примеры функциональных программ 'запись себя' через [закрытый] анализ типа

Начните с простейшей возможной функции: identity :: 'a ->' a . Сколько реализаций вы можете придумать? Если вы дадите мне , я могу сделать только одно, чтобы вернуть вам . Я возвращаю вам тот же a , который вы мне дали, так что:

let id x = x

То же самое и с парами. fst :: ('a,' b) -> 'a . Сколько способов вы можете это реализовать? Как насчет snd :: ('a,' b) -> 'b ? Для каждого может существовать только одна реализация.

Аналогично, взятие заголовка и хвоста списка выпадает прямо из fst и snd . Если head :: 'список -> и tail ::' список -> 'список и ' список - это просто пара ('a,' a list) (или пустой список), тогда очевидно, что для удовлетворения типов вы возвращаете первую и вторую часть списка соответственно .

Еще один пример, связанный с функциями высшего порядка: compose :: ('a ->' b) -> ('c ->' a) -> 'c ->' b . Есть только одна реализация, и она выпадает прямо из типов. У вас есть c и две функции. Что можно делать с c ? Что ж, вы можете применить (c -> a) . Что тогда можно сделать с a ? Единственное, что вы можете сделать, это применить (a -> b) , и вуаля, вы удовлетворили тип.

let compose f g x = f (g x)

Pipe

Вот третий пример ...

Предположим, я хочу написать функцию

p : 'a -> ('a -> 'b) -> 'b

То есть я беру в качестве аргументов значение типа 'a, и функция, которая принимает 'a и возвращает' b. И мой результат должен быть a 'b. Что ж, опять же, по модулю бесконечных циклов, исключений и инициализации по умолчанию, есть только одна реализация:

let p x f = f x

'p' может не выглядеть слишком полезным, пока вы не поймете, что это оператор конвейера (|>).

Хм, я чувствую, что эти примеры пока не впечатляют.

Карта

Еще пара, которую следует учесть ...

om2 : ('a -> 'b) -> 'a option -> 'b option

Единственная интересная реализация - Option.map:

let om f xo =
    match xo with
    | None -> None
    | Some x -> Some(f x)

Теперь я мог бы написать

let om (f:'a -> 'b) (xo:'a option) : 'b option =
    None

и просто игнорировать оба аргумента и всегда возвращать None. Но это не интересно. Кто-то передает нам все эти полезные аргументы, конечно, мы должны что-то с ними делать, право? Таким образом, первая реализация, приведенная выше, является единственной (опять же по модулю тривиальности, упомянутой в других ответах, из-за циклов, эффектов и т. Д.).

Аналогично

lm : ('a -> 'b) -> 'a list -> 'b list

Вам будет трудно написать что-либо, кроме List.map . Вы всегда можете вернуть пустой список, но это проигнорирует оба аргумента. Вы можете написать

let lm f xs =
    match xs with
    | [] -> []
    | h::t -> [f h]

, но опять же кажется странным, что кто-то передает весь этот полезный список, и мы игнорируем его все, кроме первого элемента. Если вы предполагаете, что «предназначены» для «использования» всех данных, очевидной реализацией будет List.map. (Хотя ничто не мешает вам сопоставить дважды или трижды и вернуть новый список, который в 2 или 3 раза длиннее оригинала. Еще раз, есть смысл / эстетика, в которой существует «простейшая очевидная» реализация, которая соответствует сигнатуре типа и потребляют переданные данные, и эта «очевидная» реализация полезна. Когда вы видите подпись

('a -> 'b) -> 'a list -> 'b list

, вы просто думаете «List.map», никто даже не рассматривает все другие теоретически возможные реализации, потому что все остальные - в значительной степени чепуха в контексте разработки программного обеспечения.)

Я не понимаю. Не знаю, убедительно ли это или нет.

Identity

Предположим, я хочу написать функцию f

f : 'a -> 'a

На F #, я думаю, единственная интересная реализация:

let f x = x

Вышеупомянутая функция идентификации является естественной реализацией для большинства любых язык.

И, как и в другом моем ответе, вы также можете выполнить цикл, выбросить или инициализировать по умолчанию. Но это менее интересно. Эти «бэкдоры» как бы мешают работе всех этих вычислений, «производных от типов», поэтому, возможно, лучше их игнорировать.

Ключ в этом состоит в том, что для всех типов a вы ничего не знаете о type, поэтому единственный способ «получить» реальный объект этого типа - это уже дать вам его. Так что функция идентичности - единственная разумная реализация этой подписи.

(a -> b) -> [a] -> [b]

Тип практически является реализацией.

Глупый пример стартера, следующий из моего обновления:

Дайте, что у меня есть List , как мне добраться до Array , с текущими функциями (одна добавлена ​​для обфускации!)

fn1: string -> float
fn2: List<'a> -> Array<'a>
fn3: Array<'a> -> List<'a>
fn4: ('a -> 'b) -> Array<'a> -> Array<'b>

Что ж, давайте посмотрим:

//Start at the beginning
let input:List<string> = myData
// the only thing that I can apply to this is a 
//     function that starts with List<something>, so...

input |> fn2 // List<'a> -> Array<'b>, so now I have Array<string>
// At this point, it looks like I have no choice but fn3, but that takes 
//   me back where I came from. However, there is an Array<'a> in 
//   the middle of fn4.

input |> fn2 |> fn4 ???
//oops, I need something else here, a function that goes ('a -> 'b).
//   But all my functions go ('a -> 'b)! However, in this case my 'a is a string,
//   so that limits my choice to fn1:

input |> fn2 |> fn4 fn1 // so here I have Array<float> yoohoo!

//recapitulate with the real function names
let convert input = 
    input |> Array.ofList    //List<string> -> Array<string>
          |> Array.map float //Array<string> -> (string -> float) -> Array<float>

Bottom

Хорошо, это не очень хороший пример, но «хорошо», и, возможно, он поможет реализовать некоторые другие идеи ...

Предположим,

f : unit -> 'a

То есть , Я хочу написать функцию, в которой я не передаю аргументов и которая возвращает значение любого типа. Что делает функция?

Обратите внимание, что я не могу просто вернуть 'new obj ()', поскольку сигнатура типа является универсальной, например, я могу вызвать ее с помощью f и получить обратно int, например.

Сдаться? Вот наиболее распространенная возможность:

let rec f() = f()

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

В таком языке, как Haskell, «исключения» будут «эффектами», управляемыми системой типов, но в F #:

let f() = failwith "kaboom!"

- другой пример. Если мы снова вызовем исключение, тип возвращаемого значения не имеет значения.

Наконец, детали реализации многих сред выполнения допускают «инициализацию по умолчанию» любого типа, так что, например, в F #

let f() = Unchecked.defaultof<'a>

тоже все в порядке. Я думаю, что это единственные три возможных реализации в F #.

Другой ответ - от Уэса Дайера , который упоминает именно это явление при объяснении Select для IObservable. Подпись гласила:

IObservable<U> Select<T, U>(this IObservable<T> source, Func<T, U> selector)

Я позволю вам разобраться ... (Я вполне доволен собой, мне удалось написать свой собственный Select and Where)

См.

Лучший способ сократить список типов опций до только элементов, которые не являются нет?

Вкратце, цель состоит в том, чтобы найти f здесь:

> [Some 4; None; Some 2; None] |> f;; 
val it : int list = [4; 2] 

(функция, которая проецирует только Some значений в списке ). Мой комментарий к решению (то есть List.choose id) был

Просто позвольте типам вести вас. Вам нужна функция, которая содержит опцию в своей подписи, но возвращает только список (а не список опций). Посмотрите хотя бы на API, там всего одна такая функция, выбрать, и вот вы уже на 95% справились.