Лямбда функции в haskell

Обновлено: 02.07.2024

Я пытаюсь определить функцию фильтра. Основываясь на определении функции, функция фильтра - это функция (скажем, функция справки, которая отличается от функции основного фильтра), которая принимает функцию и список для получения списка. Функция справки принимает переменную и возвращает значение типа Bool. Но, согласно строке 4, функция справки оценивает a вместе с [x], чтобы получить значение типа Bool, которое затем, наконец, возвращает список.

Могу ли я понять функцию справки как функцию, которая принимает значения a и [a] для получения значения типа Bool. Затем функция основного фильтра принимает это значение типа Bool, чтобы вернуть список?

Я знаю, что определение функции этого не предполагает, но это логично, исходя из кода. Спасибо

О каком помощнике ты говоришь? filter' является filter . Это простая рекурсивная функция, в которой filter' вызывает себя в конце входного списка.

@chepner Я думаю, что помощник - это функция, предоставленная filter . filter' используется, чтобы отличить его от настоящего filter .

@MarkNeu Он говорит о вспомогательной функции, оценивающей a , которая является предикатом, переданным в filter .

Ответы 2

Я думаю, что это будет яснее, если мы дадим функции типа a -> Bool имя, отличное от a .

Теперь f имеет типы a -> Bool , x :: a и xs :: [a] .

Почему у f нет типа a -> [a] -> Bool, потому что было бы разумнее оценивать предикат a в списке [a]. Это нелогично, что a сам по себе может быть определен как Истина или Ложь, не так ли? Функция фильтра также принимает список (второй параметр), чтобы вернуть список. Первый [a] в обозначении типа xs, а второй [a] представляет x: filter 'f xs. Большое спасибо. Я нахожу ваше объяснение наиболее понятным.

В каждой сигнатуре типа функции Haskell часть после последней стрелки является результатом функции. Здесь второй [a] - это результат - список элементов, для которых предикат истинен. Этот filter' совпадает с filter в стандартной библиотеке. Это работает для предикатов отдельных элементов. Например, filter even или filter (not . null) . Это тоже эффективно - функция учитывает каждый a ровно один раз.

Я думаю, вы упустили мою точку зрения. я понимаю, что второй [a] - это фильтр результатов 'f (x: xs) | f x == True = x: filter 'f xs То, что я не получаю, это четвертая строка, у нас уже есть функция f и x как a in (a-> Bool), но я не уверен, где реализован первый [a].

Второй аргумент filter имеет тип [a] . Этот список соответствует либо [] , либо (x:xs) . Строка filter _ [] = [] определяет, что делать, если передан пустой список. Три строки, начинающиеся с filter f (x:xs) , определяют, что делать, если передан непустой список, и связывают две переменные x и xs . Эти два случая охватывают все возможные списки.

Вы можете использовать синтаксис еще больше, чтобы облегчить понимание:

Или переведите это на более простые конструкции,

" p " - это "предикат". Он используется filter' для тестирования каждого x во входном xs , чтобы решить, следует ли включать этот x в выходные данные, в соответствии со значением Bool ean, полученным в результате тестирования.

p просто передается без изменений от одного вызова filter' к другому. Обычно это кодируется с помощью так называемого преобразования "работник-оболочка",

Наконец, более простое определение также может быть

что хорошо соответствует определению на основе foldMap

Другие вопросы по теме

Похожие вопросы

Функция haskell, которая просматривает каждую пару в списке и возвращает список с размером меньше исходного на 1

Находите ответы на сложные технические вопросы по программированию, с которыми сталкиваются инженеры по всему миру в своей ежедневной практике на сайте RedDeveloper.

Haskell или конкретный компилятор имеют что-то вроде лямбд уровня типа (если это даже термин)?

чтобы уточнить, скажем, у меня есть параметризованный тип Foo a b и хочу!--2--> быть экземпляром, скажем, функтора. Есть ли какой-либо механизм, который позволил бы мне сделать что-то похожее на

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

в то время как sclv ответил на ваш прямой вопрос, я добавлю в сторону, что существует более одного возможного значения для "лямбда уровня типа". Haskell имеет множество операторов типа, но ни один из них не ведет себя как правильный lambdas:

тип конструктора: операторы абстрактного типа, которые вводят новые типы. Учитывая тип A и конструктор типа F приложение функция F A также является типом, но не несет никакой дополнительной информации (уровень типа), чем "это F применил к A ".
полиморфных типов: типа как a -> b -> a подразумевает forall a b. a -> b -> a . The forall связывает переменные типа в пределах своей области, таким образом, ведет себя как лямбда. Если память мне не изменяет, это примерно "столичная лямбда" в системе F.
тип синонимы: ограниченная форма операторов типов, которые должны быть полностью применены и могут создавать только базовые типы и тип проектировщики.
тип занятия: по существу функции от типов / конструкторов типов до значений, с возможностью проверки аргумента типа (т. е. путем сопоставления шаблонов на конструкторах типов примерно так же, как шаблон регулярных функций соответствует конструкторам данных) и служит для определения предиката членства на типах. В некотором смысле они ведут себя как обычная функция, но очень ограничены: классы типов не являются первоклассными сущностями, которые могут быть манипулируются, и они работают на типах только как вход (не выход) и значениях только как выход (наверняка не вход).
функциональные зависимости: наряду с некоторыми другими расширениями они позволяют классам типов неявно создавать типы в качестве результатов, которые затем могут использоваться в качестве параметров для других классов типов. Все еще очень ограничен, например, неспособностью принимать другие классы типов в качестве аргументов.
тип семьи: альтернативный подход к тому, что делают функциональные зависимости; они позволяют функциям по типам определяться таким образом, который выглядит намного ближе к обычным функциям уровня значений. Однако по-прежнему действуют обычные ограничения.

другие расширения ослабляют некоторые из упомянутых ограничений или предоставляют частичные обходные пути (см. также: тип hackery Олега). Тем не менее, в значительной степени одна вещь, которую вы не можете сделать нигде, - это именно то, о чем вы спрашивали, а именно введите новую область привязки с анонимной абстракцией функции.

EHC (и, возможно, также его преемник, UHC) имеет лямбды уровня типа, но они недокументированы и не так мощны, как в зависимо типизированном языке. Я рекомендую вам использовать зависимо типизированный язык, такой как Agda (похожий на Haskell) или Coq (другой, но все же чистый функциональный по своей сути, и может быть интерпретирован и скомпилирован либо лениво или строго!) Но я предвзято отношусь к таким языкам, и это, вероятно, 100x перебор для того, что вы просите здесь!

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

но даже с -XTypeSynonymInstances-XFlexibleInstances это не работает; GHC ожидает, что тип syn будет полностью применен в головке экземпляра. Возможно, есть какой-то способ договориться с семьями типов.

Не получается пока написать evaluator, не меняя определение data Term. Насколько я понимаю, можно написать его 2 способами, используя операционную семантику (tapl, глава 5) и используя денотационную (reynolds, глава 10). Пробую начать с

Если кто-нибудь писал, поделитесь мыслями.

Лямбда-исчисление
Здравствуйте! В следующем выражении мне нужно выделить свободные и связанные переменные в термах и.

Лямбда-функции и формулы
Добрый день/вечер. Недавно пришлось начать копаться в применимости лямбда функций к доказательству.

Сравнительный анализ стандартных порядков редукции в лямбда-исчислении
Столкнулась с такой проблемой - на днях экзамен по Функциональному программированию. Дошла до.

λ-исчисление: Определите тип комбинатора: S = λfgx.fx(gx)
Здравствуйте! Хотел поинтересоваться а правильно ли я сделал задания. 2) Используя Y -.

А какие мысли вам интересны? Писал, на джаве, шарпе и своем лиспе. С выбором типа редукции - нормальным или аппликативным порядком. Самая сложность была - провести альфа-редукцию чтобы свободные переменные не становились связанными при подстановке. Вплоть до того, что имеет смысл рассмотреть нотацию Де-Брейна - ради упрощения этой задачи.

Вроде получилось (сомневаюсь в правильности),

Берем, например, комбинатор App k (App s (App k k)) = ((λx.(λy.x))((λx.(λy.(λz.((xz)(yz)))))((λx.(λy.x))(λx.(λy.x) )))) и вычисляем eval [] $ App k (App s (App k k)), получаем (λy.(λy.(λz.(λy.(λy.(λx.(λy.(yz)))))))).

Если вычисляете до головной нормальной формы, то входить внутрь тела лямбды не нужно. Сравните: в мейнстримовых языках тело функции вычисляется только после применения этой функции к конкретному аргументу.
Если же хотите-таки войти внутрь и редуцировать тело лямбды, то стоит исключить связывание свободной переменной из контекста и связанной переменной x. Способы:
1. переименовать x в e на другую переменную.
2. удалить пару (x,_) из контекста
3. добавить в контекст (x,x) на верх. lookup в качестве значения возьмём первое значение.

Для чего нужны лямбда-функции и каррирование? Когда необходимо их использовать?

А кто так говорит? Можно и без них обойтись.

А так для удобного использования ф-ий высших порядков: первое для короткой функции-аргумента, второе - для краткой записи.

По-моему эти вещи мало связаны друг с другом.

По-моему эти вещи мало связаны друг с другом

В плане использования - да, в плане реализации - нет. Каррирование реализуют через лямбды же.

Видел, что карирование часто используется в хаскеле. Из-за строгого hlint это чуть ли не необходимость. В других языках карирование встречается намного реже на мой взгляд, и оно не является уже столь необходимым. Ну, разве что, в скале свертка реализована почему-то через карирование (один фиг, передается параметром еще одна лямбда, а значит, алокатор все равно не будет спать), но вполне могли обойтись и без этого.

Карирование есть и в лиспе через библиотеку, но там, вероятно, оно используется редко.

А вот лямбды используются повсеместно, и для чего они только не используются.

Большая часть их использования - это пара к функциям типа map или fold. Вторая возможность - это использование лямбд, как возвращаемых значений у функций (высших порядков) для того, чтобы поменять поведение кода.

Как пример можно привести обработчик callback'а, которому передают лямбду возвращаемую некоторой функцией.

Не более чем сахар для работы с лямбдами, чтобы не писать что-то типа таких простыней:

Читайте также: