В чем разница между комбинатором и функцией более высокого порядка?

Question

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

Answer 1

Ну, позвольте мне попытаться получить вид определяющие их характеристики из их различных областей;)

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

функций высшего порядка

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

Типичный контекст: функциональное программирование, Haskell, любой другой (обычно набирается) язык, где функции являются гражданами первого класса (например, когда LINQ сделал C# еще более удивительным)

Фокус: пусть абонент указать/настроить некоторые функциональные возможности этой функции

комбинаторы

комбинаторы несколько специальных функций, примитивные из них даже не возражают то, что они заданы как аргументы (тип аргумента часто вообще не имеет значения, поэтому передача функций как аргументов вообще не является проблемой). Так может ли идентификатор-комбинатор также называться «функцией более высокого порядка» ??? Формально: Нет, это не нужна функция как аргумент! Но держитесь ... в каком контексте вы бы столкнулись/использовали комбинаторы (например, I, K и т. Д.) Вместо того, чтобы просто реализовать желаемую функциональность «напрямую»? Ответ: Ну, в чисто функциональном контексте!

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

Итак, основываясь на этом «слабом» законе здравого смысла, вы будете работать с комбинаторами только в чисто функциональном контексте - они по своей сути - это функции более высокого порядка. Что еще вы могли бы передать в качестве аргументов? ;)

Объединение комбинаторов (только по заявке, конечно, если вы относитесь к этому серьезно) всегда дает новые комбинаторы, которые также также являются функциями более высокого порядка. Примитивные комбинаторы обычно представляют собой простое базовое поведение или операцию (мышление комбинаторов S, K, I, Y), которые вы хотите применить к чему-то, не используя абстракции. Но, конечно, определение комбинаторов не ограничивает их с этой целью!

Типичный контекст: (нетипизированным) лямбда-исчисление, комбинаторная логика (сюрприз)

Фокус: (структурно) объединить существующие комбинаторов/"строительные блоки" для чего-то нового (например, с использованием Y-комбинатора «добавить рекурсии» к чему-то, что не является рекурсивным, пока)

Резюме

Да, как вы можете видеть, это может быть более контекстуальной/философской вещи или о том, что вы хотите выразить: я бы никогда не называть K-combinator (определение: K = \a -> \b -> a) «функция более высокого порядка» - хотя очень вероятно, что вы никогда не увидите K, вызываемого чем-то другим, кроме функций, поэтому «создание «это функция более высокого порядка.

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

EDIT: Я немного скорректировал свой ответ с тех пор - как выяснилось - это было слегка «предвзято» по личному опыту/вступлению. :) Чтобы получить еще лучшее представление о правильном распознавании комбинаторов из HOF, прочитайте комментарии ниже!

EDIT2: Взгляд на HaskellWiki также дает техническое определение комбинаторов, которое находится очень далеко от HOF!