Бессмысленный стиль Хаскеля без функций в выражении - PullRequest
Новая
       60

Бессмысленный стиль Хаскеля без функций в выражении

1 голос
/ 01 июня 2019

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

zipSorted x y = (zip . sort) y $ sort x --zipSorted(x, y) = zip(sort(y), sort(x))

и в конечном итоге преобразовал его в 

zipSorted = flip (zip . sort) . sort

(я не уверен, что это даже лучший способ сделать это, но это работает)

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

P(f, g, x, y) = f(g(y), g(x))

Тот факт, что sort присутствует дважды, но передается только один раз, намекал мне на то, что мне следует использовать оператор аппликативного функтора <*>, но я не могу понять, как по какой-то причине.

Насколько я понимаю, (f <*> g)(x) = f(x, g(x)), поэтому я попытался переписать первое бессмысленное выражение в этой форме: 

flip (zip . sort) . sort
(.) (flip $ zip . sort) sort
(flip (.)) sort $ flip (zip . sort)
(flip (.)) sort $ flip $ (zip .) sort

Кажется, что sort должно быть x, (flip (.)) должно быть f, а flip . (zip .) должно быть g. 

p = (flip (.)) <*> (flip . (zip .))
p sort [2, 1, 3] [4, 1, 5]

дает [(1, 1), (4, 2), (5, 3)], как и ожидалось, но теперь я теряюсь в том, как вытащить zip. Я пробовал 

p = (flip (.)) <*> (flip . (.))
p zip sort [2, 1, 3] [4, 1, 5]

но это не работает. Есть ли способ преобразовать это выражение в комбинатор, который выделяет zip?

Ответы [ 2 ]

6 голосов
/ 01 июня 2019

Начнем с самого начала: 

zipSort x y = zip (sort y) (sort x)

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

Здесь у нас есть общая схема «объединяющей» функции двух аргументов (здесь: zip), которым передаются два значения, преобразованные другой функцией. Если бы у нас был один и тот же базовый аргумент, но разные преобразователи, это был бы шаблон liftA2: 

  c (f x) (g x)
==
  liftA2 c f g x

Но здесь все наоборот: у нас одна и та же функция преобразования с обеих сторон (здесь: sort), но разные аргументы (x и y). Это on: 

  c (f x) (f y)
==
  (c `on` f) x y

В вашем случае мы получаем: 

zip (sort y) (sort x)
(zip `on` sort) y x
flip (zip `on` sort) x y

So 

zipSort = flip (zip `on` sort)  -- or: flip (on zip sort)

Мы можем дополнительно извлечь zip и sort, распознав стандартную композицию из двух аргументов в один аргумент: 

(\x y -> f (g x y)) == (f .) . g

1032 * дает * 

zipSort = ((flip .) . on) zip sort

Обратите внимание, что эта функция менее общая, чем точечная версия. Оригинальная функция имеет тип 

(Ord a, Ord b) => [a] -> [b] -> [(b, a)]

но у версии pointfree есть тип 

(Ord a) => [a] -> [a] -> [(a, a)]

потому что объединение двух sort s заставляет их иметь один и тот же тип.

2 голосов
/ 01 июня 2019

Я только что попросил у lambdabot ответ, вместо того, чтобы пытаться выработать его вручную: 

<amalloy> @pl \zip sort x y -> (zip . sort) y $ sort x
<lambdabot> join . (((.) . flip) .) . (.)
...