Синтаксис определения функции Haskell

Question

Я делаю конкатенацию списков следующими способами (например, используя GHC):

myConcat :: [[a]] -> [a]
myConcat xs = foldr (++) [] xs
myConcat    = foldr (++) []

Может кто-нибудь объяснить мне, пожалуйста, почему и как работают приведенные выше определения, а это не так:

myConcat xs = foldr (++) []

Является ли последняя строка кода преднамеренно недопустимой (по той причине, что конструкции могут запутаться, бесполезны и т. Д.), Или это что-то более глубокое, может быть, связано с каррированием ...

Я надеюсь, что смогу пролить свет на это, это действительно озадачивает меня: /

ПОСЛЕДНЕЕ РЕДАКТИРОВАНИЕ: Помимо приведенных ниже пояснений, я обнаружил, что хорошим источником информации по этому вопросу является раздел «Применение частичных функций и каррирование» из гл. 4 «Функциональное программирование» из книги «Real World Haskell» . Книга доступна бесплатно в Интернете.

Answer 1

Давайте рассмотрим различные версии:

myConcat xs = foldr (++) [] xs

Это обычный способ предоставления аргумента, который используется foldr. Тип [[a]] -> [a], потому что у нас есть аргумент типа [[a]] с левой стороны, который выдает [a] при подаче на правую сторону.

myConcat = foldr (++) []

Здесь foldr применяется частично, поэтому мы возвращаем функцию, которая может принимать дополнительный аргумент, список списков. Так что то, что мы получаем с правой стороны, уже то, что нам нужно, это не «синтаксический suger», а другой способ выразить то же самое, что и в первой версии. Тип снова [[a]] -> [a]: у нас ничего нет слева, но мы возвращаем функцию этой подписи справа.

myConcat xs = foldr (++) []

Здесь foldr также частично применяется, и мы возвращаем функцию, которая может принимать аргумент, как и раньше, но в нашем определении есть дополнительный аргумент xs, который не используется справа. Компилятор не «знает», что это этот аргумент, который мы хотим применить к правой стороне. Тип t -> [[a]] -> [a]. Почему?

Предположим, у вас есть квадратная функция:

sqr :: Int -> Int 
sqr x = x*x

То, что вы делаете, по сути аналогично предоставлению дополнительного неиспользуемого аргумента:

sqr:: Int -> t -> Int 
sqr x y = x*x

Функция все еще «работает», например, sqr 3 "bla" возвращает 9, но сигнатура типа отключена, а неиспользуемый аргумент ... не используется. Неиспользуемый аргумент не имеет фиксированного типа, так как он может быть практически «чем угодно», это не имеет значения. Таким образом, он получает переменную типа (t) в подписи.

Answer 2

Хорошо, давайте посмотрим на сигнатуру типа для функции curry foldr:

>:t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

То есть foldr принимает двоичную функцию (т.е. a->b->b), значение b, список значений a и возвращает значение b.

Давайте также посмотрим документацию для foldr, чтобы получить более четкое определение:

foldr, применяется к бинарному оператору, начальное значение (обычно тождество оператора), а список сокращает список, используя бинарный оператор справа налево:

Теперь давайте посмотрим на сигнатуру типа для myConcat xs = foldr (++) []

> :t myConcat
myConcat :: t -> [[a]] -> [a]

Хм ... это не то, что мы хотели ...

Проблема в том, что вы никогда не указали foldr значение типа [a]. Итак, теперь myConcat нужно какое-то значение любого типа, чтобы удовлетворить xs и значение типа [a] для завершения foldr (++) [], например:

> myConcat 2 [[1,2],[3,4]] 
[1,2,3,4]
> myConcat Nothing [[1,2],[3,4]] 
[1,2,3,4]

Это работает, но первый аргумент - просто пустая трата.

Однако, если мы передадим это xs значение foldr (++) [], например:

myConcat xs = foldr (++) [] xs

и проверьте тип подписи

> :t myConcat
myConcat :: [[a]] -> [a]

Ах, намного лучше. Теперь myConcat использует xs для завершения функции foldr.

Кроме того, myConcat = foldr (++) [] также работает и фактически является примером бессмысленного программирования в стиле . Если мы проверим тип подписи foldr (++) [],

> :t foldr (++) []
foldr (++) [] :: [[a]] -> [a]

Поскольку мы уже предоставили foldr его первые два аргумента через частичное приложение , мы возвращаем функцию, которая принимает значение [[a]] и делает то, что мы хотим! Поэтому мы просто присваиваем его имени, и оно работает так же, как в примере выше, но нам не нужно явно передавать аргументы!

> let myConcat = foldr (++) []
> :t myConcat
myConcat :: [[a]] -> [a]
> myConcat [[1,2],[3,4]]
[1,2,3,4]

Answer 3

myConcat xs = foldr (++) []

имеет тип t -> [[a]] -> [a], который отличается от типа двух других [[a]] -> [a].