haskell 二叉树同态定理的应用

ki0zmccv  于 2023-01-21  发布在  其他
关注(0)|答案(1)|浏览(156)

我知道存在以下问题:
haskell - How to quickcheck applicative homomorphism property? - Stack Overflow
然而,以下PRAGMA的引入

{-# LANGUAGE ScopedTypeVariables #-}

并没有解决我的问题。
以下是我的定义:

{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}

module Laws where

import Control.Applicative ((<$>), liftA3)

import Data.Monoid

import Test.QuickCheck
import Test.QuickCheck.Function
import Test.QuickCheck.Gen

data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Show, Eq)

instance Functor BinTree where
    fmap _ Empty = Empty
    fmap f (Node x hi hd) = Node (f x) (fmap f hi) (fmap f hd)

instance Applicative BinTree where
    -- pure :: a -> BinTree a
    pure x = Node x (pure x) (pure x)

    -- <*> :: BinTree (a -> b) -> BinTree a -> BinTree b
    _ <*> Empty = Empty -- L1, 
    Empty <*> t = Empty
    (Node f l r) <*> (Node x l' r') = Node (f x) (l <*> l') (r <*> r')

instance (Arbitrary a) => Arbitrary (BinTree a) where
    arbitrary = oneof [return Empty, -- oneof :: [Gen a] -> Gen a
                liftA3 Node arbitrary arbitrary arbitrary]
                
-- Identity
apIdentityProp :: (Applicative f, Eq (f a)) => f a -> Bool
apIdentityProp v = (pure id <*> v) == v

-- pure f <*> pure x = pure (f x)   -- Homomorphism
apHomomorphismProp :: forall f a b. (Applicative f, Eq (f b)) => Fun a b -> a -> Bool
apHomomorphismProp (apply -> g) x = (((pure g :: f (a -> b)) <*> (pure x :: f a)) :: f b) == (pure (g x) :: f b)

main :: IO ()
main = quickCheck (apHomomorphismProp :: Fun Int Int -> Int -> Bool)

如何修复以下错误?
无法从上下文推导出**(应用f0)(适用f,方程式(f B))**

kmpatx3s

kmpatx3s1#

如果包含完整的错误消息,其中提到了一个 ambiguous type variable,那么分析这个问题就会更容易一些。GHC抱怨的是f没有出现在apHomomorphismProp的类型签名中的任何地方,除了在量词和约束中。
为什么这是个问题呢?嗯,它 * 不是 * 问题......但是它曾经出现在旧的Haskell版本中,因为编译器没有办法告诉当你 * 使用 * apHomomorphismProp时,它应该在这里测试什么应用程序。事实上,你使用它的方式仍然是这样的:apHomomorphismProp :: Fun Int Int -> Int -> Bool并没有以任何方式提到BinTree,那么编译器怎么知道这是您的意思呢?就编译器所知,您还不如要求在这里测试Maybe应用程序。
在现代的Haskell中,解决方案是-XTypeApplications,它只允许您显式地指定应该使用什么类型的变量进行示例化。

{-# LANGUAGE TypeApplications #-}

main = quickCheck (apHomomorphismProp @BinTree :: Fun Int Int -> Int -> Bool)

事实上,我建议使用以下语法来澄清Int类型:

main = quickCheck $ apHomomorphismProp @BinTree @Int @Int

但是,apHomomorphismProp仍然存在编译错误,这是因为在TypeApplications之前,类似于apHomomorphismProp的签名是无用的。但是这个限制现在已经过时了†,并且可以在-XAllowAmbiguousTypes中禁用:

{-# LANGUAGE ScopedTypeVariables, UnicodeSyntax, AllowAmbiguousTypes, TypeApplications #-}

apHomomorphismProp :: ∀ f a b. (Applicative f, Eq (f b)) => Fun a b -> a -> Bool
apHomomorphismProp (apply -> g) x = (pure @f g <*> pure x) == pure (g x)

注意,我只需要为其中一个pure提到@f,其他的都自动地被约束为相同的应用。
†它是否真的“过时”是有争议的。可能仍然正确的是,如果初学者给他们的函数一个模糊的类型,它更有可能是一个错误,应该当场抓住,而不是实际上打算用于-XTypeApplications。一个无意的模糊类型可以导致相当混乱的错误进一步行。

相关问题