Для чего еще можно использовать функцию `loeb`?

Ответ 1

Первичным источником (я думаю) для loeb является блог Dan Piponi, The Neighborhood of Infinity. Там он объясняет всю концепцию более подробно. Я немного повторю это в качестве ответа и добавлю несколько примеров.

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 value a x, чтобы быть вычисленным. Возможно, это более ясно написано как (изоморфное) Functor a => Reader (a x) x, подчеркивая, что это просто значение x, которое задерживается, ожидая контекста (a x), который будет создан.

type Delay q x = q -> x

Используя эти идеи, мы можем описать loeb следующим образом. Нам дается Functor, содержащая некоторые значения Delay ed

Functor f => f (Delay q x)

Естественно, если бы нам дали a 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 ed значения. Одним из естественных примеров этого является использование примеров списка до

> 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 ed.

В комментарии Chris Kuklewicz отмечается, что не так много можно сделать с 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

поэтому мы можем также написать это напрямую.

Ответ 2

Вы можете использовать его для динамического программирования. Примером, который приходит на ум, является алгоритм Smith-Waterman.

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)

Ответ 3

Вот живой пример, где он используется для: Map String Float

http://tryplayg.herokuapp.com/try/spreadsheet.hs/edit

с обнаружением петли и разрешением контура.

Эта программа вычисляет скорость, время и пространство. Каждый из них зависит от двух других. Каждая ячейка имеет два значения: текущее введенное значение и выражение как функцию других значений/выражений ячейки. округление разрешено.

Код перерасчета ячеек использует известное выражение loeb Дэн Пипони в 2006 году. До сих пор, насколько я знаю, материализации этой формулы на реальной рабочей таблице не было. это близко к нему. Поскольку loeb входит в бесконечный цикл, когда используются круговые выражения, программа подсчитывает петли и уменьшает сложность, постепенно подставляя формулы по значениям ячеек, пока выражение не будет иметь петли

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

Это сообщение в блоге:

http://haskell-web.blogspot.com.es/2014/09/spreadsheet-like-program-in-browser.html