Точечный свободный стиль, необходимый для оптимизированного Карри

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

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]]

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

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

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

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

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

В стороне, я также не уверен, почему работает обертка both; pointfree стиль realFunction ведет себя как версия pointfree стиля contrived в том, что частичное приложение оценивается только один раз (т. е. если something отсортировать a, то это будет сделано только один раз). По-видимому, поскольку both не является беспредметным, у Хаскелла должна быть та же проблема, что и с беспредметным contrived.

1 2
haskell partial-application pointfree currying

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 сохраняется для всех будущих вызовов.

2