Как применить функцию более высокого порядка к эффективной функции в Haskell?

У меня тоже есть функции:

higherOrderPure :: (a -> b) -> c
effectful :: Monad m => (a -> m b)

Я бы применил первую функцию ко второй:

higherOrderPure `someOp` effectful :: Monad m => m c

где

someOp :: Monad m => ((a -> b) -> c) -> (a -> m b) -> m c

Пример:

curve :: (Double -> Double) -> Dia Any 
curve f = fromVertices $ map p2 [(x, f x) | x <- [1..100]]

func :: Double -> Either String Double
func _ = Left "Parse error" -- in other cases this func can be a useful arithmetic computation as a Right value

someOp :: ((Double -> Double) -> Dia Any) -> (Double -> Either String Double) -> Either String (Dia Any)
someOp = ???

curve `someOp` func :: Either String (Dia Any)

Ответ 1

Тип

Monad m => ((a -> b) -> c) -> (a -> m b) -> m c

не заселен, т.е. нет такого термина t, имеющего этот тип (если вы не используете дивергенцию, например бесконечную рекурсию, error, undefined и т.д.).

Это означает, что, к сожалению, невозможно реализовать оператор someOp.

Proof

Чтобы доказать, что невозможно построить такое t, мы протекаем от противного. Предположим, что существует t с типом

t :: Monad m => ((a -> b) -> c) -> (a -> m b) -> m c

Теперь специализируйте c до (a -> b). Получим

t :: Monad m => ((a -> b) -> a -> b) -> (a -> m b) -> m (a -> b)

Следовательно

t id :: Monad m => (a -> m b) -> m (a -> b)

Затем специализируйте монаду m на продолжении monad (* -> r) -> r

t id :: (a -> (b -> r) -> r) -> ((a -> b) -> r) -> r

Далее специализируйте r до a

t id :: (a -> (b -> a) -> a) -> ((a -> b) -> a) -> a

Итак, получим

t id const :: ((a -> b) -> a) -> a

Наконец, используя изоморфизм Карри-Говарда, мы получаем, что следующая интуиционистская тавтология:

((A -> B) -> A) -> A

Но вышеприведенный известный закон

Ответ 2

Я думаю, вы можете достичь того, чего хотите, написав монадическую версию curve:

curveM :: Monad m => (Double -> m Double) -> m (QDiagram B R2 Any)
curveM f = do
    let xs = [1..100]
    ys <- mapM f xs
    let pts = map p2 $ zip xs ys
    return $ fromVertices pts

Это можно легко записать короче, но у вас есть тот тип, который вы хотите. Это аналогично map -> mapM и zipWith -> zipWithM. Монадические версии функций должны быть разделены на разные реализации.

Чтобы проверить:

func1, func2 :: Double -> Either String Double
func1 x = if x < 1000 then Right x else Left "Too large"
func2 x = if x < 10   then Right x else Left "Too large"

> curveM func1
Right (_ :: QDiagram B R2 Any)
> curveM func2
Left "Too large"