Для чего еще можно использовать функцию `loeb`?
Я пытаюсь понять "Löb and möb: странные петли в Хаскеле", но сейчас значение от меня ускользает, я просто не понимаю, почему это может быть полезно. Просто чтобы вспомнить функцию loeb определяется как
loeb :: Functor f => f (f a -> a) -> f a
loeb x = go where go = fmap ($ go) x
или эквивалентно:
loeb x = go
where go = fmap (\z -> z go) x
В статье есть пример с [] Реализация functor и электронных таблиц, но для меня это немного чуждо, как и сами электронные таблицы (никогда не использовал их).
Хотя я понимаю эту электронную таблицу, я думаю, что мне и другим было бы полезно иметь больше примеров, несмотря на списки. Есть ли приложение для loeb за Maybe или другие функторы?
3 ответа
Основной источник (я думаю) для loeb это блог Дэна Пипони " Соседство бесконечности". Там он объясняет всю концепцию более подробно. Я напишу немного об этом в качестве ответа и добавлю несколько примеров.
loeb реализует странную ленивую рекурсию
loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x
Давайте представим, что у нас есть a-алгебра, функция типа Functor a => a x -> x, Вы можете думать об этом как о способе вычисления значения из структуры значений. Например, вот несколько []-алгебрами
length :: [Int] -> Int
(!! 3) :: [a] -> a
const 3 :: Num a => [a] -> a
\l -> l !! 2 + l !! 3 :: Num a => [a] -> a
мы можем видеть, что эти a-алгебры могут использовать оба значения, хранящиеся в Functor и структура Functor сам.
Еще один способ думать о d :: Functor a => a x -> x в качестве значения x который требует некоторого контекста, целого значения Functorized a x, для того чтобы быть вычисленным. Возможно, это более четко написано как (изоморфный) Functor a => Reader (a x) x, подчеркивая, что это просто значение x который задерживается в ожидании (a x) контекст должен быть произведен.
type Delay q x = q -> x
Используя эти идеи, мы можем описать loeb следующее. Нам дают Functor содержащий некоторые DelayEd значения
Functor f => f (Delay q x)
Естественно, если бы нам дали q тогда мы могли бы преобразовать это в неотложную форму. На самом деле, мы можем написать такую функцию
force :: Functor f => f (Delay q x) -> q -> f x
force f q = fmap ($ q) f
Какие loeb делает это обрабатывать дополнительный сложный случай, когда q на самом деле f x, сам результат этой функции. Если вы знакомы с fixИменно так мы можем получить этот результат.
loeb :: Functor a => a (Delay (a x) x) -> a x
loeb f = fix (force f)
Таким образом, чтобы сделать пример, мы просто должны построить Functor содержащий Delayпод ред. Одним из естественных примеров этого является использование списка примеров из ранее
> loeb [ length :: [Int] -> Int
, const 3 :: [Int] -> Int
, const 5 :: [Int] -> Int
, (!! 2) :: [Int] -> Int
, (\l -> l !! 2 + l !! 3) :: [Int] -> Int
]
[5, 3, 5, 5, 10]
Здесь мы видим, что список полон значений с задержкой в ожидании результата оценки списка. Это вычисление может быть выполнено именно потому, что в зависимости от данных нет циклов, поэтому все это можно просто определить лениво. Например, const 3 а также const 5 оба сразу доступны как значения. length требует, чтобы мы знали длину списка, но ни одно из содержащихся в нем значений, поэтому он также сразу переходит к нашему списку фиксированной длины. Интересными являются значения с отложенным ожиданием других значений из нашего списка результатов, но так как (!! 2) заканчивается только в зависимости от третьего значения списка результатов, которое определяется const 5 и, таким образом, может быть немедленно доступно, вычисление продвигается вперед. Та же самая идея происходит с (\l -> l !! 2 + l !! 3),
Итак, вот оно: loeb завершает этот странный вид рекурсии с задержкой значения. Мы можем использовать его на любом виде Functor, хоть. Все, что нам нужно сделать, это подумать о некоторых полезных Delayпод ред.
В комментарии Криса Куклевича отмечается, что мало что можно было бы сделать интересно Maybe как твой функтор. Это потому, что все задержанные значения более Maybe принять форму
maybe (default :: a) (f :: a -> a) :: Maybe a -> a
и все интересные ценности Maybe (Delay (Maybe a) a) должно быть Just (maybe default f) поскольку loeb Nothing = Nothing, Итак, в конце дня default значение никогда даже не привыкает --- у нас всегда это есть
loeb (Just (maybe default f)) == fix f
так что мы можем написать это напрямую.
Вы можете использовать его для динамического программирования. Пример, который приходит на ум - алгоритм Смита-Уотермана.
import Data.Array
import Data.List
import Control.Monad
data Base = T | C | A | G deriving (Eq,Show)
data Diff = Sub Base Base | Id Base | Del Base | Ins Base deriving (Eq,Show)
loeb x = let go = fmap ($ go) x in go
s a b = if a == b then 1 else 0
smithWaterman a' b' = let
[al,bl] = map length [a',b']
[a,b] = zipWith (\l s -> array (1,s) $ zip [1..] l) [a',b'] [al,bl]
h = loeb $ array ((0,0),(al,bl)) $
[((x,0),const 0) | x <- [0 .. al]] ++
[((0,y),const 0) | y <- [1 .. bl]] ++
[((x,y),\h' -> maximum [
0,
(h' ! (x - 1,y - 1)) + s (a ! x) (b ! y),
(h' ! (x - 1, y)) + 1,
(h' ! (x, y - 1)) + 1
]
) | x <- [1 .. al], y <- [1 .. bl]]
ml l (0,0) = l
ml l (x,0) = ml (Del (a ! x): l) (x - 1, 0)
ml l (0,y) = ml (Ins (b ! y): l) (0, y - 1)
ml l (x,y) = let
(p,e) = maximumBy ((`ap` snd) . (. fst) . (const .) . (. (h !)) . compare . (h !) . fst) [
((x - 1,y),Del (a ! x)),
((y, x - 1),Ins (b ! y)),
((y - 1, x - 1),if a ! x == b ! y then Id (a ! x) else Sub (a ! x) (b ! y))
]
in ml (e : l) p
in ml [] (al,bl)
Вот живой пример, где он используется для: Map String Float
http://tryplayg.herokuapp.com/try/spreadsheet.hs/edit
с обнаружением петли и разрешением петли.
Эта программа рассчитывает скорость, время и пространство. Каждый зависит от двух других. Каждая ячейка имеет два значения: его текущее введенное значение и выражение в зависимости от значений / выражений других ячеек. круглость разрешена.
Код перерасчета ячейки использует знаменитое выражение loeb Дана Пипони в 2006 году. До сих пор, насколько мне известно, не было никакой материализации этой формулы в реальной рабочей таблице. этот близок к этому. Поскольку loeb входит в бесконечный цикл при использовании круговых выражений, программа считает циклы и уменьшает сложность, постепенно заменяя формулы значениями ячеек, пока в выражении не будет циклов
Эта программа сконфигурирована для немедленного пересчета при смене соты, но она может быть адаптирована для изменения более чем одной соты перед перерасчетом путем ее запуска с помощью кнопки.
Это блог pos:
http://haskell-web.blogspot.com.es/2014/09/spreadsheet-like-program-in-browser.html