Поднимите функцию более высокого порядка в монаду

Question

Предположим, у меня есть функция более высокого порядка, которая выполняет некоторые вычисления с использованием значений, которые она извлекает из ее функционального параметра.

f :: a -> (b -> c) -> d 

где a, b, c, d - некоторые конкретные типы.

Тогда у меня есть функция этого типа

g :: b -> m c 

где т некоторая монада.

Теперь есть способ использовать g с f. Это поворот f в функцию, которая производит m d вместо d и может использовать g в качестве второго параметра?

Конкретным примером может быть то, что m является монадой IO, f является функцией, вычисляющей сумму n чисел, полученных из ее функционального параметра, и g считывает число из стандартного ввода.

f n g = sum $ map g (1..n) 
g :: Int -> IO Int 
g _ = readLn 

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

Предположим, у меня есть алгоритм для выполнения чего-то на графике. Алгоритм использует функциональный параметр для определения соседей узла. Это так, что я могу иметь несколько реализаций графика.

Теперь я хочу использовать этот алгоритм с недетерминированным графом (List monad) или графиком, который не полностью известен (возможно, монада). Я знаю, что я мог бы переписать алгоритм для использования монад, а затем использовать монодацию для основного случая, но это единственный способ? Я думаю, было бы легче написать алгоритм без монад.

Возможно ли такое поведение? Я не мог найти причину, почему это не должно быть, но я не смог найти способ, как это сделать.

Answer 1

Вы хотите, например, Получают mapMmap. То есть у вас есть простой map:

map :: (a -> b) -> [a] -> [b] 

и вы хотите использовать его в качестве map on monadic structures

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

Мы можем вычислить mapM от map путем сопоставления действия ввода-вывода, а затем секвенирования их, таким образом:

mapM f xs = sequence (map f xs) 

И теперь у нас есть более общая форма, мы можем вернуться map, запустив mapM в the Identity monad., а затем классический map - mapM в удостоверении личности.

> let g :: Int -> Identity Int 
     g a = return (a^2) 

где:

> runIdentity $ mapM g [1..10] 
[1,4,9,16,25,36,49,64,81,100] 

Так что да, вы должны generlize вашу функцию высшего порядка до нужного уровня - будь то монада, или функтор, или аппликативны, то вы можете заменить в другие понятия вычисления, включая идентичность.

Вы можете механически переписать любую чистую функцию его монадическим, по transformting АСТ для функции:

• оберточного значение результата в return
• идентифицировать недавно монадическое подвыражение, и их связывание.
• заменяет привязку переменной с монадическим связыванием; или, если это аппликативны:
• замена приложение с применением в монаде (с некоторой осторожности)

Э.Г.

map f []  = [] 
map f (x:xs) = f x : map f xs 

К (аппликативный стиль)

mapM f []  = return [] 
mapM f (x:xs) = (:) <$> f x <*> mapM' f xs 

или менее ясно, и фиксируя порядок оценки:

mapM f []  = return [] 
mapM f (x:xs) = do 
    v <- f x 
    vs <- mapM f xs 
    return (v:vs) 

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

foldl  :: (a -> b -> a) -> a -> [b] -> a 
foldl f z0 xs0 = lgo z0 xs0 
    where 
     lgo z []  = z 
     lgo z (x:xs) = lgo (f z x) xs 

foldlM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a 
foldlM f z0 xs0 = lgo z0 xs0 
    where 
     lgo z []  = return z 
     lgo z (x:xs) = do 
      v <- f z x 
      lgo v xs