如何在Haskell中将高阶函数应用于有效函数？

Question

我也有功能:

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)

Answer 1

类型

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

没有人居住,即不存在长期t具有类型(除非你利用的分歧,比如无限递归error,undefined等等).

遗憾的是,这意味着不可能实现操作员someOp.

证明

为了证明构建这样的a是不可能的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)

然后,将monad专门化为mcontinuation 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

但上面是众所周知的皮尔士定律,这在直觉逻辑中是不可证明的.因此,我们获得了矛盾.

结论

以上证明t不能以一般方式实施,即在任何单子中工作.在特定的monad中,这仍然是可能的.

Answer 2

我认为你可以通过编写一个monadic版本来实现你想要的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.函数的monadic版本必须分成不同的实现.

去测试:

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"