Point Free проблемы в Хаскеле

Question

Я пытаюсь преобразовать следующий код на haskell в свободный стиль, но безрезультатно.

bar f g xs = filter f (map g xs )

Я новичок в Haskell, и любая помощь будет отличной

Answer 1

Преобразование в стиль без точек может быть выполнено полностью механически, хотя это сложно, если вы не знакомы с основами синтаксиса Haskell, такими как применение левой ассоциативной функции и x + y быть таким же, как (+) x y, Я предполагаю, что вы знакомы с синтаксисом Haskell; в противном случае я предлагаю сначала пройти первые несколько глав ЛЯХ.

Вам нужны следующие комбинаторы, которые есть в стандартной библиотеке. Я также дал их стандартные имена из исчисления комбинаторов.

id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

Работайте с одним параметром одновременно. Переместите параметры слева в лямбды справа, например

f x y = Z

становится

f = \x -> \y -> Z

Мне нравится делать это один аргумент за раз, а не все сразу, это просто выглядит чище.

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

1. Если у вас есть \x -> x, заменить id
2. Если у вас есть \x -> A, где A любое выражение, в котором x не происходит, заменить на const A
3. Если у вас есть \x -> A x, где x не происходит в A, заменить A, Это известно как "сокращение ЭТА".
4. Если у вас есть \x -> A B, затем
   1. Если x происходит в обоих A а также B, заменить (\x -> A) <*> (\x -> B),
   2. Если x происходит только A, заменить flip (\x -> A) B
   3. Если x происходит только B, заменить A . (\x -> B),
   4. Если x не встречается ни в одном A или же BНу, есть еще одно правило, которое мы уже должны были использовать.

А затем работайте вовнутрь, уничтожая созданные вами лямбды. Давайте работать с этим примером:

f x y z = foo z (bar x y)
-- Move parameter to lambda:
f x y = \z -> foo z (bar x y)
-- Remember that application is left-associative, so this is the same as
f x y = \z -> (foo z) (bar x y)
-- z appears on the left and not on the right, use flip
f x y = flip (\z -> foo z) (bar x y)
-- Use rule (3) 
f x y = flip foo (bar x y)

-- Next parameter
f x = \y -> flip foo (bar x y)
-- Application is left-associative
f x = \y -> (flip foo) (bar x y)
-- y occurs on the right but not the left, use (.)
f x = flip foo . (\y -> bar x y)
-- Use rule 3
f x = flip foo . bar x

-- Next parameter
f = \x -> flip foo . bar x
-- We need to rewrite this operator into normal application style
f = \x -> (.) (flip foo) (bar x)
-- Application is left-associative
f = \x -> ((.) (flip foo)) (bar x)
-- x appears on the right but not the left, use (.)
f = ((.) (flip foo)) . (\x -> bar x)
-- use rule (3)
f = ((.) (flip foo)) . bar
-- Redundant parentheses
f = (.) (flip foo) . bar

Ну вот, попробуй на своем! На самом деле нет никакой хитрости в принятии решения о том, какое правило использовать: используйте любое применяемое правило, и вы добьетесь прогресса.

Answer 2

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

Первые три шага действительно просты и состоят в удалении общего x из чего-то вида h x = f (g x) написав h = f . g, По сути, это говорит: "Если вы можете написать вещь в форме a $ b $ c $ ... $ y $ z и вы хотите удалить zпоменяйте все доллары на точки, a . b . c . ... . y:

bar f g xs = filter f (map g xs)
           = filter f $ (map g xs)
           = filter f $ map g $ xs -- because a $ b $ c == a $ (b $ c).
bar f g    = filter f . map g
           = (filter f .) (map g)
           = (filter f .) $ map $ g
bar f      = (filter f .) . map

Так что это последнее f это единственная сложная часть, и это сложно, потому что f не в "конце" выражения. Но, глядя на это, мы видим, что это функциональный раздел (. map) применяется к остальной части выражения:

bar f = (.) (filter f) . map
bar f = (. map) $ (.) $ filter $ f
bar   = (. map) . (.) . filter

и вот как вы уменьшаете выражение, когда у вас нет таких сложных вещей, как f x x и тому подобное появляется в нем. В общем есть функция flip f x y = f y x который "переворачивает аргументы"; Вы всегда можете использовать это для перемещения f с другой стороны. Здесь мы имеем flip (.) map . (.) . filter если вы включите явный обратный вызов.

Answer 3

Я попросил lambdabot, робота, который работает на различных IRC-каналах Haskell, автоматически определить бессмысленный эквивалент. Команда@pl(бессмысленно).

10:41 <frase> @pl bar f g xs = filter f (map g xs )
10:41 <lambdabot> bar = (. map) . (.) . filter

Точка бесплатной версииbarявляется:

bar = (. map) . (.) . filter

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

Наконец, если вам не нужен IRC, существуют конвертеры без точек, такие как Blunt(@TaylorFausak),pointfree программа командной строки и другие инструменты.