Haskell / Miranda: найдите тип функции

Question

Вкратце: это прошлый экзаменационный вопрос на экзамене в Миранде, но синтаксис очень похож на Haskell.

Вопрос: Каков тип следующего выражения и что оно делает? (Определения функций length и swap приведены ниже).

(foldr (+) 0) . (foldr ((:) . length . (swap (:) [] )) [])

length [] = 0

length (x:xs) = 1 + length xs

swap f x y = f y x

Замечания:

Пожалуйста, не стесняйтесь отвечать в синтаксисе haskell - извините за использование звездочек в качестве политипов, но я не хотел переводить их неправильно в haskell. По сути, если одна переменная имеет тип *, а другая - *, это означает, что они могут быть любого типа, но оба они должны быть одного типа. Если у вас есть **, то это означает, что он может иметь тот же тип, что и *. Я думаю, что это соответствует a, b, c и т. Д. В использовании haskell.

Моя работа до сих пор

Из определения длины вы можете увидеть, что он находит длину списка чего-либо, так что это дает

length :: [*] -> num.

Из определения я думаю, что swap принимает функцию и два параметра и производит функцию с двумя переключенными параметрами, так что это дает

swap :: (* -> ** -> ***) -> ** -> [*] -> ***

Foldr принимает двоичную функцию (например, плюс) начальное значение и список и сворачивает список справа налево, используя эту функцию. Это дает

foldr :: (* -> ** -> **) -> ** -> [*] -> **)

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

Функция foldr выводит одно значение (результат свертывания списка), поэтому я знаю, что возвращаемый тип будет неким типом политипа, а не списком политипа.

Моя проблема

Я не уверен, куда идти отсюда на самом деле. Я вижу, что своп должен принимать другой аргумент, поэтому подразумевает ли это частичное приложение, что все это функция? Я совсем запутался!

Answer 1

Вы уже получили ответ, я просто запишу деривацию шаг за шагом, чтобы было легко увидеть все сразу:

xxf xs = foldr (+) 0 . foldr ((:) . length . flip (:) []) [] $ xs
       == sum $ foldr ((:) . length . (: [])) [] xs
       == sum $ foldr (\x -> (:) (length [x])) [] xs
       == sum $ foldr (\x r -> length [x]:r) [] xs
       == sum $ map   (\x -> length [x]) xs
       == sum [length [x] | x <- xs]  
       == sum [1 | x <- xs]
    -- == length xs
xxf :: (Num n) => [a] -> n

Так что в Миранде xxf xs = #xs, Я думаю, что его тип :: [*] -> num в синтаксисе Миранды.

Хаскеля length является :: [a] -> Int но, как определено здесь, это :: (Num n) => [a] -> n потому что он использует Num"s (+) и два литерала, 0 а также 1,

Если у вас возникли проблемы с визуализацией foldrэто просто

foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...))))))
          == a+(b+(c+(d+(e+(...+(z+ 0)...)))))
          == sum [a,b,c,d,e,...,z]

Answer 2

Давайте пройдемся по этому шаг за шагом.

length функция, очевидно, имеет тип, который вы описали; в Хаскеле это Num n => [a] -> n, Эквивалентная функция Хаскеля length (Оно использует Int вместо любого Num n).

swap Функция принимает функцию для вызова и отменяет свои первые два аргумента. Вы не совсем правильно поняли подпись; его (a -> b -> c) -> b -> a -> c, Эквивалентная функция Хаскеля flip,

foldr функция имеет тип, который вы описали; а именно (a -> b -> b) -> b -> [a] -> b, Эквивалентная функция Хаскеля foldr,

Теперь давайте посмотрим, что означает каждое подвыражение в основном выражении.

Выражение swap (:) [] принимает (:) функция и меняет свои аргументы. (:) функция имеет тип a -> [a] -> [a], так swap пинг это дает [a] -> a -> [a]; таким образом, все выражение имеет тип a -> [a] потому что поменялась функция применяется к [], В результате получается, что функция создает список из одного элемента, заданного этим элементом.

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

singleton :: a -> [a]
singleton = swap (:) []

Теперь следующее выражение (:) . length . singleton, (:) функция все еще имеет тип a -> [a] -> [a]; что за (.) Функция делает то, что она составляет функции, так что если у вас есть функция foo :: a -> ... и функция bar :: b -> a, foo . bar будет иметь тип b -> ..., Выражение (:) . length таким образом имеет тип Num n => [a] -> [n] -> [n] (Помните, что length возвращает Num) и выражение (:) . length . singleton имеет тип Num => a -> [n] -> [n], То, что делает полученное выражение, довольно странно: при любом значении типа a и какой-то список, он будет игнорировать a и добавьте число 1 в этот список.

Для простоты давайте сделаем из этого функцию:

constPrependOne :: Num n => a -> [n] -> [n]
constPrependOne = (:) . length . singleton

Вы уже должны быть знакомы с foldr, Он выполняет правое сворачивание по списку с помощью функции. В этой ситуации это вызывает constPrependOne на каждом элементе, поэтому выражение foldr constPrependOne [] просто строит список единиц с равной длиной для списка ввода. Итак, давайте сделаем функцию из этого:

listOfOnesWithSameLength :: Num n => [a] -> [n]
listOfOnesWithSameLength = foldr constPrependOne []

Если у вас есть список [2, 4, 7, 2, 5], ты получишь [1, 1, 1, 1, 1] при подаче заявления listOfOnesWithSameLength,

Затем foldr (+) 0 функция является еще одной правой. Это эквивалентно sum функция в Хаскеле; суммирует элементы списка.

Итак, давайте сделаем функцию:

sum :: Num n => [n] -> n
sum = foldr (+) 0

Если вы сейчас составляете функции:

func = sum . listOfOnesWithSameLength

... вы получите результирующее выражение. Учитывая некоторый список, он создает список равной длины, состоящий только из одних, а затем суммирует элементы этого списка. Другими словами, ведет себя так же, как length, только используя гораздо более медленный алгоритм. Итак, последняя функция:

inefficientLength :: Num n => [a] -> n
inefficientLength = sum . listOfOnesWithSameLength