Означает ли «ограничение значений» практически отсутствие функционального программирования более высокого порядка?

Question

Означает ли "ограничение значений" практически, что функционального программирования более высокого порядка не существует?

У меня проблема в том, что каждый раз, когда я пытаюсь сделать немного HOP, я попадаюсь на ошибку VR. Пример:

let simple (s:string)= fun rq->1 
let oops= simple ""

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)  
let oops2= get ""

и я хотел бы знать, является ли это проблемой частичной реализации VR или это общая проблема, которая не имеет решения на языке с изменяемым типом, который не включает мутации в системе типов.

Answer 1

Означает ли «ограничение значений», что функционального программирования более высокого порядка не существует?

Абсолютно нет! Ограничение значений практически не мешает функциональному программированию высшего порядка. То, что делает , ограничивает некоторые применения полиморфных функций & mdash; not функций высшего порядка & mdash; на верхнем уровне.

---

Давайте посмотрим на ваш пример. Ваша проблема в том, что oops и oops2 являются функцией идентификации и имеют тип forall 'a . 'a -> 'a. Другими словами, каждый является полиморфным значением. Но правая часть не является так называемым «синтаксическим значением»; это функциональное приложение. (Приложению-функции не разрешено возвращать полиморфное значение, потому что в противном случае вы могли бы создать взломанную функцию, используя изменяемые ссылки и списки, которые могли бы подорвать систему типов; то есть вы могли бы написать тип завершающей функции типа forall 'a 'b . 'a -> 'b.

К счастью, почти во всех практических случаях рассматриваемое полиморфное значение является функцией, и вы можете определить ее с помощью расширения eta:

let oops x = simple "" x

Эта идиома выглядит так, как будто у нее есть некоторые затраты времени выполнения, но в зависимости от встроенного модуля и оптимизатора, от которых может избавиться компилятор - это просто плохая проверка типов, которая испытывает проблемы.

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

let oops2 = F(fun x -> let F f = get "" in f x)

Это довольно утомительно, но анонимная функция fun x -> ... является синтаксическим значением, а F является конструктором типа данных, а конструктор, примененный к синтаксическому значению, также является синтаксическим значением, и Боб - ваш дядя , Упаковка и распаковка F будут скомпилированы в функцию идентификации, поэтому oops2 собирается скомпилировать в точно тот же машинный код, что и oops.

Все еще хуже, если вы хотите, чтобы вычисления во время выполнения возвращали полиморфное значение, например None или []. Как намекнул Натан Сандерс, вы можете столкнуться с ограничением значения с помощью простого выражения rev []:

Standard ML of New Jersey v110.67 [built: Sun Oct 19 17:18:14 2008]
- val l = rev [];
stdIn:1.5-1.15 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val l = [] : ?.X1 list
-  

Ничего более высокого порядка там нет! И все же действует ограничение стоимости.

На практике ограничение значения не представляет препятствия для определения и использования функций более высокого порядка ; ты просто эта-расширяйся.

Answer 2

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

Для этого конкретного примера в F # можно восстановить обобщение с помощью аннотации типа и явного параметра типа:

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)  
let oops2<'T> : 'T SimpleType = get ""

Answer 3

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

Очевидно, что мы не собираемся писать выражение rev [] в программе, поэтому не имеет особого значения, что оно не полиморфно. Но что, если мы создадим функцию, используя вызов функции? С помощью функций карри мы делаем это постоянно:

- val revlists = map rev;

Здесь ревлисты должны быть полиморфными, но ограничение по значению портит нас:

- val revlists = map rev;
stdIn:32.1-32.23 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val revlists = fn : ?.X1 list list -> ?.X1 list list

К счастью, есть простой трюк, который мы можем использовать, чтобы сделать ревлисты полиморфными. Мы можем заменить определение revlists на

- val revlists = (fn xs => map rev xs);
val revlists = fn : 'a list list -> 'a list list

и теперь все работает просто отлично, поскольку (fn xs => map rev xs) является синтаксическим значением. (Эквивалентно, мы могли бы использовать более распространенный забавный синтаксис:

- fun revlists xs = map rev xs;
val revlists = fn : 'a list list -> 'a list list

с тем же результатом.) В литературе хитрость замены функционально-выраженного выражения e на (fn x => e x) называется расширением eta. Опытным путем было установлено, что расширения eta обычно достаточно для того, чтобы справиться с ограничением значения.

Подводя итог, нельзя сказать, что программирование высшего порядка ограничено настолько, насколько бессмысленное программирование. Это может объяснить некоторые проблемы, возникающие у меня при переводе кода на Haskell на F #.

---

Редактировать: В частности, вот как исправить ваш первый пример:

let simple (s:string)= fun rq->1 
let oops= (fun x -> simple "" x)     (* eta-expand oops *)

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)
let oops2= get ""

Я еще не понял второй, потому что мешает конструктор типов.