(Вдохновлен моим ответом на этот вопрос .)
Рассмотрим этот код (он должен найти самый большой элемент, который меньше или равен заданному входу):
data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)
closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing where
precise :: Maybe (Integer, v) -> TreeMap v -> Maybe (Integer, v)
precise closestSoFar Leaf = closestSoFar
precise closestSoFar (Node k v l r) = case i `compare` k of
LT -> precise closestSoFar l
EQ -> Just (k, v)
GT -> precise (Just (k, v)) r
Это не очень лениво. После того, как GT
дело введено, мы точно знаем, что окончательное возвращаемое значение будет Just
чем-то Nothing
, а Just
не до конца. Я хотел бы сделать это более ленивым, чтобы Just
он был доступен, как только GT
дело введено. Мой тестовый пример для этого, что я хочу Data.Maybe.isJust $ closestLess 5 (Node 3 () Leaf undefined)
оценить, True
а не дно. Вот один из способов сделать это:
data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)
closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess _ Leaf = Nothing
closestLess i (Node k v l r) = case i `compare` k of
LT -> closestLess i l
EQ -> Just (k, v)
GT -> Just (precise (k, v) r)
where
precise :: (Integer, v) -> TreeMap v -> (Integer, v)
precise closestSoFar Leaf = closestSoFar
precise closestSoFar (Node k v l r) = case i `compare` k of
LT -> precise closestSoFar l
EQ -> (k, v)
GT -> precise (k, v) r
Однако сейчас я повторяюсь: основная логика теперь closestLess
и в, и в precise
. Как я могу написать это так, чтобы это было лениво, но не повторялось?
источник
Начиная с моей не ленивой реализации, я сначала рефакторинг,
precise
чтобы получитьJust
в качестве аргумента, и обобщил его тип соответственно:Затем я изменил это, чтобы сделать
wrap
рано и вызвать себяid
вGT
случае:Это по-прежнему работает точно так же, как и раньше, за исключением добавленной лени.
источник
id
промежуточныеJust
и финальные значения(k,v)
устранены компилятором? скорее всего, нет, функции должны быть непрозрачными, и вы могли бы (возможно, по типу) использовать ихfirst (1+)
вместо того,id
чтобы все, что знает компилятор. но это делает для компактного кода ... конечно, мой код - это распутывание и спецификация вашего здесь с дополнительным упрощением (устранениеid
s). также очень интересно, как более общий тип служит в качестве ограничения, отношения между задействованными значениями (хотя и недостаточно жесткими, сfirst (1+)
разрешением aswrap
).precise
используется в двух типах, непосредственно соответствующих двум специализированным функциям, используемым в более подробном варианте. там хорошее взаимодействие Кроме того, я бы не назвал этот CPS,wrap
он не используется в качестве продолжения, он не создается "изнутри", он складывается - путем рекурсии - снаружи. Может быть , если бы были использованы в качестве продолжения вы могли бы избавиться от этих постороннихid
с ... Кстати , мы можем увидеть здесь еще раз , что старый образец функционального аргумента используется как индикатор того , что делать, переключение между двумя курсами действия (Just
илиid
).Я думаю, что версия CPS, на которую вы ответили сами, является лучшей, но для полноты изложения приведу еще несколько идей. (РЕДАКТИРОВАТЬ: ответ Бура в настоящее время является наиболее эффективным.)
Первая идея состоит в том, чтобы избавиться от "
closestSoFar
" аккумулятора, и вместо этого позволитьGT
регистру обрабатывать всю логику выбора самого правого значения, наименьшего из аргумента. В этой формеGT
кейс может напрямую вернутьJust
:Это проще, но занимает больше места в стеке, когда вы сталкиваетесь с большим количеством
GT
случаев. Технически вы могли бы даже использовать этоfromMaybe
в форме аккумулятора (т.fromJust
Е. Заменить неявное в ответе Луки), но это было бы избыточной, недоступной ветвью.Другая идея состоит в том, что на самом деле есть две «фазы» алгоритма, одна до и одна после того, как вы нажали a
GT
, поэтому вы параметризуете его логическим значением для представления этих двух фаз и используете зависимые типы для кодирования инварианта, что всегда будет результат на втором этапе.источник
Как насчет
?
источник
Just
но является полным. Я знаю, что ваше решение в том виде, в котором оно написано, на самом деле является полным, но оно хрупкое в том смысле, что казалось бы безопасная модификация может привести к его падению.Just
, поэтому он добавит тест, чтобы убедиться, что он неNothing
каждый раз повторяется.Мало того, что мы всегда знаем
Just
, после его первого открытия, мы также всегда знаемNothing
до тех пор. Это на самом деле две разные "логики".Итак, в первую очередь мы идем налево, так что сделайте это явно:
Цена повторяется не более одного шага не более одного раза.
источник