Функция карты SML

Вы сказали:

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

Что ж, имейте в виду, что в Standard ML (и, в целом, во всех прикладных языках) нет такой вещи, как «функция n параметров» для «n», кроме 1. Однако функции более чем одного Параметр можно смоделировать двумя способами:

1. Как функции одного параметра, который является кортежем или записью. Исходные предполагаемые параметры могут быть восстановлены в теле функции посредством проецирования из кортежа или записи.

2. Как функции первого параметра, возвращающие функцию остальных параметров.

Имея это в виду, мы проверяем тип map в REPL:

> map;
val it = fn: ('a -> 'b) -> 'a list -> 'b list

(Я использую Poly / ML, а не SML / NJ, но, если не считать проблем с форматированием, результат должен быть таким же.)

Ни кортежей, ни записей. map явно использует второй подход к моделированию функции двух параметров: он принимает функцию типа 'a -> 'b и возвращает другую функцию типа 'a list -> 'b list.

Теперь вот загвоздка: для любой функции foo, map foo также является функцией! Поскольку map может принимать любую функцию в качестве аргумента, map foo сам по себе является вполне законным аргументом для map. Это означает, что map (map foo) проверка типов для любой функции foo. В частности, это верно, если val foo = fn x => [x].

Вы сказали:

Кажется, что для этого недостаточно аргументов.

Если он проверяет тип, он запускается.

Вы сказали:

Если я сбегу

map (fn x => [x]) [[], [1], [2,3,4]]

я получил

val it = [[[]], [[1]], [[2,3,4]]];

Для меня это имеет больше смысла, поскольку он берет каждый элемент в списке и переносит его в другой список. Но когда я кладу на нее другую карту, она меняет вывод.

Давайте немного реорганизуем ваш код, не меняя его смысла:

let
  val foo = fn x => [x]
  val bar = map foo
  val baz = map bar
in
  baz [[], [1], [2,3,4]]
end

Теперь мы можем проанализировать, что каждая функция (foo, bar, baz) делает со своим параметром:

1. foo берет единственный элемент x и помещает его в конструктор данных списка.
2. bar принимает список элементов, обертывает каждый элемент в конструкторе данных списка и возвращает список с результирующими обернутыми элементами (список списков).
3. baz берет (супер) список (под) списков элементов, применяет bar к каждому подсписку и возвращает список с результатами.

Выполните все это вручную, чтобы убедиться, что результат [[], [[1]], [[2], [3], [4]]] действительно правильный.

 map ;
 val it = fn : ('a -> 'b) -> 'a list -> 'b list

поэтому map принимает функцию, которая снова берет список и дает список.

Итак, определите карту с функцией

-fun f x = x+1 ;
val f = fn : int -> int
-map f ;
val it = fn : int list -> int list

теперь it - это тот тип функции, которая принимает список и возвращает список

- it [1,2] ;
val it = [2,3] : int list

Я думаю, что функция карты понятна