Действительно “Оценивает Ограничение”, практически среднее, что нет никакого функционального программирования высшего порядка?

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

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

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

Еще хуже, когда вы хотите, чтобы вычисление во время выполнения возвращало полиморфное значение, например 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
-  

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

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

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

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

 - val revlists = map rev; 
 

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

 - val revlists = map rev; 
stdIn: 32.1-32.23 Предупреждение: переменные типа, не обобщенные из-за ограничения значения 
, создаются для фиктивных типов (X1, X2, ...) 
val revlists = fn:? .X1 list list ->? .X1 list list 
 

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

 - val revlists = (fn xs => map rev xs); 
val revlists = fn: 'список списка ->' список списка 
 

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

 - fun revlists xs = map rev xs; 
val revlists = fn: 'список списка ->' список списка 
 

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

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

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

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 ""

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

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

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

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