Типы в Haskell
Я являюсь довольно новым в Haskell, и я испытываю затруднения при понимании как выведенные типы и такие работы.
map :: (a -> b) -> [a] -> [b]
(.) :: (a -> b) -> (c -> a) -> c -> b
Что ТОЧНО, который означает?
foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl1 :: (a -> a -> a) -> [a] -> a
Каковы различия между ними?
И выведенный тип
foldr map [a] -> [a -> a] -> [a]
Но почему это - это?
Спасибо!
4 ответа
Если взять пример с
map :: (a -> b) -> [a] -> [b]
Это означает, что map принимает 2 аргумента
- Функция от типа a к типу b
- Список типа a
И возвращает
- Список b
Вы уже видите здесь закономерность, но она станет яснее, если мы заменим 'a' и 'b'
- a = String
- b = Int
Таким образом, это определение типа будет
map :: (String -> Int) -> [String] -> [Int]
Итак, теперь это функция, которая принимает String и возвращает Int, а также список Strings и возвращает список Ints.
Скажем, наша функция, которая принимает String и возвращает Int, будет read. read использует строку, которую вы ей даете, чтобы преобразовать ее во что-то другое. Поскольку здесь мы поместили ее в контекст Int, она преобразует строку в int
map read ["1", "2", "112", 333"]
В результате получится
[1, 2, 112, 333]
потому что map берет вашу функцию read и maps (применяет) ее к каждому элементу списка. Вам не нужно говорить read, что это аргумент, как read "1", или read n, потому что map позаботится об этом за вас.
И это действительно все. Тип функции говорит только о том, какие типы она принимает и какой тип возвращает. Конечно, есть еще куррирование, но к нему вы вернетесь позже, специально или нет! В основном это означает, что функция принимает не много аргументов, а только один. Скажем, возьмем функцию +. Если вы оцените 1+2, она вернет функцию, которая принимает другое число, которое прибавляется к 1, и поскольку здесь есть другое число, 2, она будет использовать его. Вы могли бы оценить его как (1+) и передать его дальше, возможно, добавив число некоторое время спустя. Это более понятно, когда у вас нет инфиксного синтаксиса +. Можно было бы написать (+) 1 2, тогда сначала это утверждение становится (+) 1 , которое имеет тип (упрощенный! Я не буду вводить здесь типокласс Num) Int -> Int. Таким образом, (+) 1 (или (1+), если на то пошло) - это просто ДРУГАЯ функция, к которой вы можете применить значение, и тогда результат сможет вычисляться до 3.
Вот как это выглядит на практике: (Игнорируйте часть (Num a) =>, если она вас смущает, это концепция, о которой вы узнаете позже. Просто замените здесь типы a на Int, если хотите, и полностью игнорируйте часть (Num a) =>.)
(+) :: (Num a) => a -> a -> a
(+2) :: (Num a) => a -> a
(1+) :: (Num a) => a -> a
(1+2) :: (Num a) => a
Prelude> (+2) 5
7
Prelude> map (+3) [1,2,3]
[4,5,6]
И на ваш второй вопрос: вы не определяете инферентные типы вообще. Они называются "inferred", потому что компилятор/интерпретатор "вычисляет" (читай: вычисляет) типы сам, без того, чтобы вы их явно называли.
О foldX различиях: Все они делают одно и то же: сокращают список до одного значения. Разница между функциями заключается лишь во внутреннем определении. foldl сворачивает список слева, а foldr - справа.
Таким образом, чтобы сложить список, вы можете использовать все из них следующим образом...
foldl1 (+) [1,2,3] == 6
foldr (+) 0 [1,2,3] == 6
foldl (+) 0 [1,2,3] == 6
Видите ли, кроме foldl1, вы предоставляете функцию для сложения, начальное значение (аккумулятор) и список для сложения. fold1 имеет свой собственный аккумулятор, вы не передаете ему свой.
На практике лучше использовать foldr, потому что в отличие от fold он подходит для работы с БОЛЬШИМИ списками без сбоев из-за переполнения стека (ти, хи). Исключением из этого правила является foldl' (обратите внимание на "'"!) в Data.Map - это строгая складка, которая также подходит для больших списков.
Если вы хотите сами задавать функциям их типы (если вы их написали), рассмотрите этот пример:
double :: Int -> Int
double n = 2 * n
Или по-хаскелловски
double :: Int -> Int
double = (*2)
Первая строка обоих примеров (double :: Int -> Int) - это то, что вы ищете. Именно так вы можете заставить компилятор или интерпретатор определить функцию - вы можете опустить ее, а компилятор/интерпретатор сам найдет ее (и иногда даже лучшим способом, чем можно подумать)
Функции в Haskell используют нотацию, называемую каррированием. Определение типа
plus :: Int -> Int -> Int
означает, что плюс - это функция, которая принимает два Int s и возвращает значение самого правого типа (опять же Int ). . Более подробно, каррирование означает, что вы работаете с частично применяемыми функциями, что позволяет вам писать такой код, как
plus1 :: Int -> Int
plus1 = plus 1
Строчные идентификаторы в сигнатурах типов указывают на так называемую переменную типа , которую можно рассматривать как заполнитель для любых возможный тип.
Таким образом, определение
map :: (a -> b) -> [a] -> [b]
означает Для любых типов a и b , map принимает функцию из a в b и список из a , из которого создается список b .
Возьмем пример
map show [1, 2, 3]
Мы видим, что данный список является списком Int , поэтому a = Int . Кроме того, map должен применять show к каждому элементу, который возвращает String .Поскольку show должно соответствовать типу a -> b из определения, мы можем вывести, что b = String .
Наше выражение возвращает [b] , поэтому результатом будет [String] .
Чтобы сделать такие подписи еще более понятными, мы можем написать их, используя более подробный синтаксис
map :: forall a b . (a -> b) -> [a] -> [b]
Теперь здесь явно указано, что карта должна работать со всеми типами a и ] b .
Что касается складок, посмотрите их определения . Учитывая вышеизложенное, сигнатуры типов должны быть самоочевидными, когда ясно , что функции должны делать.
Пример: факториал n = foldl (*) 1 [1..n]
Подпись foldr map становится.
foldr map :: [a] -> [a -> a] -> [a]
Вы также можете получить их, просто набрав : t foldr map в интерпретаторе Haskell (GHCi).
Строчные буквы в объявлениях типов являются переменными типа. Это означает, что когда есть a, это должен быть тот же тип.
Подвыражения в скобках (например, (a -> b)) обычно означают, что функция принимает функцию в качестве одного из своих параметров.
Прямоугольные скобки указывают на список чего-либо.
Так map принимает такие аргументы:
(a -> b)функция, принимающая один аргумент[a]список, над которым может действовать функция первого аргумента
и выдает [b] список в качестве результата.
Мы можем расшифровать (.) таким же образом:
(a -> b)- это функция, принимающая один аргумент(c -> a)- это функция, которая производит тот же тип, что и аргумент первой функцииc- аргумент того же типа, который использует вторая функция
Однако Haskell может делать изящную вещь, и если вы опускаете аргумент, он возвращает функцию с оставшейся сигнатурой. Так, (.) обычно используется для создания цепочки функций.
Допустим, у нас есть две функции ord :: Char -> Int, которая принимает символ и возвращает его целочисленное представление, и add32 :: Int -> Int, которая прибавляет 32 к аргументу.
Когда мы пишем upcaseVal = add32 . ord, функция upcaseVal теперь имеет сигнатуру upcaseVal :: Char -> Int, потому что функция (.) оставила бы c -> b, а мы подставляем их в определение функции.
Поэтому foldr map должна была бы выглядеть так:
Первый аргумент foldr- это функция, принимающая 2 аргумента, которой являетсяmap.- Так как выход функции должен быть того же типа, что и второй аргумент (
(a -> b -> b), мы видим, что вmapa = b
Таким образом, окончательный тип будет:
(b -> b) -> [b] -> [b] -> b -> [b] -> b
Но я думаю, это не должно вас так сильно беспокоить, поскольку компилятор имеет дело с подобными вещами большую часть времени.
В Haskell переменная в нижнем регистре является переменной типа. В то время как Char просто означает Char , a или b может означать Char или Bool ] или Целое число или другой тип. Ключ в том, что все будут одного типа. И все b будут одного типа.
Например, map принимает в качестве первого аргумента функцию, которая принимает одну переменную типа a и возвращает другую типа b . Затем map возвращает новую функцию, которая принимает список типа a . Эта новая функция возвращает список типа b .
Предположим, у вас есть функция increment , которая прибавляет единицу к целому числу. приращение карты [1,2,3] в конечном итоге вернет список [2,3,4].
Предыдущее определение map с замененными типами переменных выглядело бы так:
map :: increment -> [1,2,3] -> [2,3,4]
и инкремент , кстати, будет выглядеть как
increment :: Integer -> Integer
Причина, по которой это написано смешно, состоит в том, что вы можете частично применять функции. Здесь я создам новую функцию, основанную на частичном применении map:
incrementList = map increment
Затем вы можете использовать
incrementList [1,2,3]
, который даст тот же результат