Правильное понимание логики предварительного вычисления F # - PullRequest
Новая
       6

Правильное понимание логики предварительного вычисления F #

3 голосов
/ 09 апреля 2020

Этот вопрос расширен из моего предыдущего вопроса о изменяемом значении. Я почти уверен, что основная тема c этого вопроса, предварительное вычисление имеет много общего со связанным вопросом.

Пожалуйста, посмотрите примеры ниже, которые я привел из книги, с которой я учусь: 

let isWord (words : string list) =
    let wordTable = Set.ofList words     // Expensive computation!
    fun w -> wordTable.Contains(w)

val isWord : words:string list -> (string -> bool)

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

let isCapital = isWord ["London"; "Paris"; "Warsaw"; "Tokyo"];;
val isCapital : (string -> bool)

let isCapitalSlow word = isWord ["London"; "Paris"; "Warsaw"; "Tokyo"] word
val isCapitalSlow : (string -> bool)

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

Как я узнал в классе PL, по порядку Чтобы оценить выражение лямбда-исчисления, каждый параметр должен быть дан телу. Отсутствие только одного не позволит выразить выражение.

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

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

Кажется, что эта часть может сильно влияет на оптимизацию и производительность, поэтому я хочу, чтобы мое понимание этого топи c ясно.

Ответы [ 2 ]

3 голосов
/ 09 апреля 2020

Я пришел к выводу, что у первого нет параметров, поэтому он может сразу начинать оценку, когда задан список, но второй не может начинать оценку, пока не задано слово параметра.

Это совершенно верно.

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

По сути, это тоже правильно, но это проще, чем ваша формулировка. «Отсутствие информации» не является чем-то очень сложным - это просто тот факт, что лямбда-функции являются значениями и не могут быть оценены, пока их параметры не указаны.

Это может быть немного легче понять, если мы переписываем все с использованием записи fun x -> ..: 

let isWord = fun (words : string list) =
    let wordTable = Set.ofList words
    fun w -> wordTable.Contains(w)

let isCapital = 
  isWord ["London"; "Paris"; "Warsaw"; "Tokyo"]

let isCapitalSlow = fun word -> 
  isWord ["London"; "Paris"; "Warsaw"; "Tokyo"] word

Оценка продолжается сверху вниз.

  1. Выражение, присвоенное isWord, является функцией, поэтому тело не может быть оценено.
  2. Выражение, присвоенное isCapital, является приложением функции, поэтому его можно оценить , Это, в свою очередь, оценивает значение wordTable и возвращает функцию, которая является функцией и не может быть оценена.
  3. Выражение, присвоенное isCapitalSlow, является функцией и не может быть оценено.
  4. Если позже вы вызовете isCapitalSlow "Prague", это будет приложение-функция, и его можно будет оценить. Затем он вызовет isWord со списком городов в качестве аргумента, который, в свою очередь, вызовет Set.ofList для построения wordTable и выдаст функцию, которая затем будет оценена с word в качестве аргумента.
1 голос
/ 09 апреля 2020

Поскольку вы, похоже, знакомы с C#, мы можем переписать его как C# класс: 

class IsWord
{
    HashSet<string> set;
    public IsWord(string[] words) => set = new HashSet<string>(words);
    public bool Contains(string word) => set.Contains(word);
}

Как бы выглядели эквивалентные функции? 

Func<string, bool> isCapital = 
    new IsWord(new[] { "London", "Paris", "Warsaw", "Tokyo" }).Contains;

Func<string, bool> isCapitalSlow = 
    (word) => new IsWord(new[] { "London", "Paris", "Warsaw", "Tokyo" }).Contains(word);

Обратите внимание, что isCapital создает экземпляр класса один раз и возвращает его содержащий метод. Поэтому каждый раз, когда вы звоните isCapital, вы на самом деле звоните только HashSet.Contains.

В isCapitalSlow вы создаете экземпляр IsWord и, в свою очередь, HashSet каждый раз Вы называете метод. Это, естественно, будет медленнее.

В идиоматическом c F # вы бы написали это как: 

let isWord words =
    let wordTable = Set.ofList words     
    let contains word = wordTable |> Set.contains word
    contains
...