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

Question

Краткое описание: Это экзамен на экзамене с экзамена Миранда, но синтаксис очень похож на Haskell.

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

(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 usuage.

Мой работает до сих пор

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

length :: [*] -> num. 

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

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

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

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, очевидно, имеет тип, который вы описали; в Haskell это Num n => [a] -> n. Эквивалентная функция Haskell - length (она использует Int вместо Num n).

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

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

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

Выражение swap (:) [] выполняет функцию (:) и свопит аргументы. Функция (:) имеет тип a -> [a] -> [a], поэтому swap ping дает [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 в Haskell; он суммирует элементы списка.

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

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

Если теперь составляют функции:

func = sum . listOfOnesWithSameLength 

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

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