Тип функции в SML - PullRequest
Новая
       38

Тип функции в SML

0 голосов
/ 12 февраля 2011

Может кто-нибудь объяснить мне, почему тип функции, приведенной ниже, является
('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Функция: 

fun foldr f b [] = b 
  | foldr f b (x::xs) = f (x, (foldr f b xs))

Когда я смотрю на эту функцию, я обнаруживаю, что тип должен быть просто ('a * 'b -> 'b) -> 'b, поскольку у нас есть функция f, которая принимает кортеж и просто возвращает значение 'b, а также в базовом случае мы возвращаем 'b.

Ответы [ 2 ]

4 голосов
/ 12 февраля 2011

Чтобы определить тип функции, процесс в основном выглядит так:

С учетом функции, 

fun foldr f b []      = b
  | foldr f b (x::xs) = f (x, (foldr f b xs))

предполагается, что все типы параметров и возвращаемое значение неизвестны. 

foldr   : 'a -> 'b -> 'c -> 'd
f (arg1): 'a
b (arg2): 'b
  (arg3): 'c
(return): 'd

fun foldr f b []      = b

Прежде всего, мы видим, что b (arg2) совпадает с типом возврата foldr (return) и (arg3) является списком некоторого неизвестного типа. 

f (arg1): 'a
b (arg2): 'b
  (arg3): 'e list
(return): 'b

  | foldr f b (x::xs)

x и xs составляют список (arg3). 

f (arg1): 'a
b (arg2): 'b
  (arg3): 'e list
(return): 'b
x       : 'e
xs      : 'e list

                      = f (x, (foldr f b xs))

Тогда f (arg1) - это функция, которая принимает 2-кортеж и возвращает тот же тип, что и foldr return (return). Первый элемент кортежа того же типа, что и x. Второй элемент кортежа того же типа, что и тип возвращаемого значения foldr (возврат). Типы также сохраняются для рекурсивного вызова foldr. 

f (arg1): 'e * 'b -> 'b
b (arg2): 'b
  (arg3): 'e list
(return): 'b
x       : 'e
xs      : 'e list

fun foldr f b []      = b
  | foldr f b (x::xs) = f (x, (foldr f b xs))

Это не может быть упрощено, поэтому у нас есть тип:

Foldr: ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

1 голос
/ 12 февраля 2011

Я думаю, что приведенный выше код для foldr неверен;это должно быть 

fun  foldr f b [] = b 
   | foldr f b (x::xs) = (f x (foldr f b xs))

То есть, оно не должно передавать кортеж аргументов, а, скорее, передает аккумулятор и рекурсивный вызов foldr в качестве аргументов как обычно.* Относительно того, откуда происходит тип, помните, что foldr принимает три параметра:

  1. Функция, применяемая в диапазоне.
  2. Начальное значение аккумулятора.
  3. Диапазон, в котором можно сложить.

Предположим, что аккумулятор имеет тип 'b, а список имеет тип 'blist.Мы знаем, что общий возвращаемый тип функции должен быть 'b, потому что у нас есть 

fun  foldr f b [] = b

Давайте теперь посмотрим, что является типом f.У нас есть это: 

foldr f b (x::xs) = (f x (foldr f b xs))

Это берет первый элемент списка и аккумулятор, затем производит что-то, что должно быть типа 'b.Список имеет тип 'a list, а аккумулятор имеет тип 'b, поэтому функция имеет тип ('a * 'b -> 'b).

Подводя итог, тип функции 

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

О чем и сообщается.

...