Для оптимизированного карри необходим стиль без точек

Question

Скажем, у нас есть (надуманная) функция, например:

import Data.List (sort)

contrived :: Ord a => [a] -> [a] -> [a]
contrived a b = (sort a) ++ b

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

map (contrived [3,2,1]) [[4],[5],[6]]

На первый взгляд, это работает так, как можно было бы ожидать:

[[1,2,3,4],[1,2,3,5],[1,2,3,6]]

Однако, если мы бросим некоторые traces в:

import Debug.Trace (trace)

contrived :: Ord a => [a] -> [a] -> [a]
contrived a b = (trace "sorted" $ sort a) ++ b
map (contrived $ trace "a value" [3,2,1]) [[4],[5],[6]]

Мы видим, что первый список передан в contrived оценивается только один раз, но сортируется для каждого элемента в [4,5,6]:

[sorted
a value
[1,2,3,4],sorted
[1,2,3,5],sorted
[1,2,3,6]]

Сейчас, contrived можно довольно просто перевести на бессмысленный стиль:

contrived :: Ord a => [a] -> [a] -> [a]
contrived a = (++) (sort a)

Который при частичном применении:

map (contrived [3,2,1]) [4,5,6]

Все еще работает, как мы ожидаем:

[[1,2,3,4],[1,2,3,5],[1,2,3,6]]

Но если мы снова добавим traces:

contrived :: Ord a => [a] -> [a] -> [a]
contrived a = (++) (trace "sorted" $ sort a)
map (contrived $ trace "a value" [3,2,1]) [[4],[5],[6]]

Мы видим, что теперь первый список перешел в contrived оценивается и сортируется только один раз:

[sorted
a value
[1,2,3,4],[1,2,3,5],[1,2,3,6]]

Почему это так? Поскольку перевод в стиль pointfree настолько тривиален, почему GHC не может сделать вывод, что ему нужно только отсортировать a однажды в первой версии contrived?

---

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

realFunction a b = conditionOne && conditionTwo
  where conditionOne = map (something a) b
        conditionTwo = somethingElse a b

В стиле pointfree для этого требуется написать некрасивую оболочку (both) вокруг (&&):

realFunction a = both conditionOne conditionTwo
  where conditionOne = map (something a)
        conditionTwo = somethingElse a
        both f g x = (f x) && (g x)

Кроме того, я также не уверен, почему both обертка работает; бессмысленный стиль realFunction ведет себя как бессмысленная версия стиля contrived в том, что частичное заявление оценивается только один раз (т.е. если something отсортированный a это будет сделано только один раз). Похоже, что с both это не проблема, у Haskell должна быть та же проблема, что и с contrived,

Answer 1

Если я правильно понимаю, вы ищете это:

contrived :: Ord a => [a] -> [a] -> [a]
contrived a = let a' = sort a in \b -> a' ++ b
                    -- or ... in (a' ++)

Если вы хотите, чтобы сортировка вычислялась только один раз, это должно быть сделано до \b,

Вы правы в том, что компилятор может оптимизировать это. Это называется оптимизацией "полной лени".

Если я правильно помню, GHC не всегда делает это, потому что это не всегда фактическая оптимизация, в общем случае. Рассмотрим надуманный пример

foo :: Int -> Int -> Int
foo x y = let a = [1..x] in length a + y

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

При частичном применении xзакрытие для foo x требуется только O(1) памяти, так как список еще не сгенерирован. Код как

let f = foo 1000 in f 10 + f 20  -- (*)

по-прежнему бегать в постоянном пространстве.

Вместо этого, если мы написали

foo :: Int -> Int -> Int
foo x = let a = [1..x] in (length a +)

затем (*) больше не будет работать в постоянном пространстве. Первый звонок f 10 выделит список длиной 1000 и сохранит его в памяти для второго вызова f 20,

---

Обратите внимание, что ваше частичное заявление

... = (++) (sort a)

по существу означает

... = let a' = sort a in \b -> a' ++ b

так как передача аргумента включает в себя привязку, как в let, Итак, результат вашего sort a хранится для всех будущих звонков.