Понимание типов функций - PullRequest
Новая
       15

Понимание типов функций

3 голосов
/ 30 мая 2019

Я пытаюсь понять типы функций и могу объяснить их.

Две функции: 

insert :: t -> Bool -> ([t],[t]) -> ([t],[t])
insert a True (b,c) = (a:b,c)
insert a False (b,c) = (b,a:c)

partition :: (t -> Bool) -> [t] -> ([t],[t])
partition p [] = ([],[])
partition p (x : xs) = insert x (p x) (partition p xs)

Из моих ограниченных знаний я думаю, что функция вставки:

  • insert относится к типу t, принимает два аргумента: bool и один из кортежа двух списков типа t и возвращает кортеж из двух списков типа t.

  • partition - это кортеж типа t, который возвращает значение типа bool, в качестве аргумента он принимает список типа t и возвращает кортеж из двух списков типа t.

Это правильный образ мышления или я ошибаюсь?Я следовал некоторым учебникам, и это то, что я понял до сих пор.

Ответы [ 3 ]

10 голосов
/ 30 мая 2019

insert имеет тип t, он принимает два аргумента: один из Bool и один из кортежа из двух списков типа t и возвращает кортеж из двух списков типа t.

Нет .Прежде всего важно отметить, что в Haskell каждая функция принимает ровно один параметр.Действительно, 

insert :: t -> Bool -> ([t],[t]) -> ([t],[t])

- это короткая и компактная форма: 

insert :: t -> (Bool -> (([t],[t]) -> ([t],[t])))

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

insert :: ((->) t) (((->) Bool) (((->) ((,) ([] t)) ([] t))  ((,) ([] t)) ([] t)))

, но вышесказанное, конечно, не очень читабельно, поэтому давайте придерживаться второй формы.

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

Так что, если бы мы сгенерировали выражение insert x, мы построили функциютип Bool -> (([t], [t]) -> ([t], [t])).

Неформально , иногда действительно говорят, что " функция принимает n параметров ".Но важно помнить об этом.

Во-вторых, вы забыли о t.Неформально можно сказать, что insert принимает три параметра, значение типа t, логическое значение (тип Bool) и 2-кортеж с двумя списками t с.Он вернет 2 кортежа из двух списков t с.В зависимости от того, Bool равен True или False, он добавляет к одному из двух списков заданное значение.

Например: 

Prelude> insert 5 False ([], [])
([],[5])
Prelude> insert 5 False ([1,4], [2,5])
([1,4],[5,2,5])
Prelude> insert 5 True ([1,4], [2,5])
([5,1,4],[2,5])
Prelude> insert 3 True ([1,4], [2,5])
([3,1,4],[2,5])
Prelude> insert 3 False ([1,4], [2,5])
([1,4],[3,2,5])

partition - это кортеж типа t, который возвращает bool, и он принимает список типа t в качестве аргумента и возвращает кортеж из двух списков типа t.

Нет, здесь параметр имеет тип (t -> Bool), то есть функция .Действительно, в Haskell вы можете передавать функции в качестве параметров.

Неформально мы можем сказать, что partition принимает " предикат " (функция, которая отображает значения в Bool s) и списокt с, и он возвращает 2-кортеж с двумя списками t с.В зависимости от того, верен ли предикат для значений в списке, они сортируются в первом или втором списке в кортеже 2.

Например: 

Prelude> partition (>3) [1,4,2,5]
([4,5],[1,2])
Prelude> partition (>3) [1,3,0,2]
([],[1,3,0,2])
Prelude> partition (>3) [1,7,8,0]
([7,8],[1,0])
Prelude> partition (>3) [1,7,8,9]
([7,8,9],[1])
6 голосов
/ 30 мая 2019

Нет, типы в точности такие, как показано:

insert имеет тип t -> Bool -> ([t], [t]) -> ([t], [t]), что означает, что это функция, которая принимает значение типа t в качестве аргумента и возвращает функцию типа Bool -> ([t], [t]) -> ([t], [t]). Неформально вы можете думать о insert как о функции, которая принимает 3 аргумента: один из типа t, один из типа Bool и один из типа ([t], [t]), и возвращает другое значение типа ([t], [t]).

partition - это функция, которая принимает другую функцию (типа t -> Bool) в качестве аргумента и возвращает функцию типа [t] -> ([t],[t]). Неформально, опять же, вы можете думать о partition как о получении двух аргументов (типа t -> Bool и типа [t]) и возвращении значения типа ([t], [t]).

-> сам по себе является оператором уровня типа; он принимает два типа в качестве аргументов и возвращает тип функции. Это правоассоциативно, что означает a -> (b -> c) и a -> b -> c эквивалентны.

5 голосов
/ 30 мая 2019

Нет, insert - это функция , поэтому она не может быть "типа t". Если бы он был типа t, это было бы значение : 

a :: Int
a = 5

Здесь a является типа Int.

Как видно из реализации функции, insert принимает три аргумента: 

insert a True (b,c) = ...

Аргументы: a, True и (b, c).

Итак, тип insert точно равен t -> Bool -> ([t],[t]) -> ([t],[t]):

  1. это функция (из-за -> с)
  2. ... из один аргумент из некоторый тип t
  3. ... и возвращает другую функцию типа Bool -> ([t],[t]) -> ([t],[t])
    1. ... который принимает один аргумент типа Bool (и только Bool)
    2. ... и возвращает функцию ([t],[t]) -> ([t],[t])
    3. (это должен быть один уровень глубины отступа) ... который принимает один аргумент типа ([t],[t]) (кортеж из двух списков, каждый из которых содержит значения some type t)
    4. ... и возвращает, наконец, значение типа ([t],[t])

Теперь это выглядит как беспорядок: функции, возвращающие другие функции, которые возвращают функции ... Но это можно упростить. Вы можете думать о insert как о функции трех аргументов:

  1. insert - это сумасшедшая функция, которая возвращает другие функции: введите t -> Bool -> ([t],[t]) -> ([t],[t])
  2. insert 2 относится к типу Bool -> ([t],[t]) -> ([t],[t])
  3. insert 2 True если типа ([t],[t]) -> ([t],[t])
  4. insert 2 True ([1], [2]) относится к типу ([t],[t])

BOOM! Последний вызов фактически вернул значение, а не функцию! И благодаря этому можно insert рассматривать как функцию трех аргументов. Эта вещь называется карри и названа в честь того же человека, в честь которого назван Хаскелл - Хаскелла Карри.

...