使用 GADT 在 Haskell 中重新创建 Lisp 的“应用”
Recreating Lisp's `apply` in Haskell using GADTs
作为练习,我正在尝试在 Haskell 中重新创建 Lisp 的 apply
。我不打算将它用于任何实际目的,我只是认为这是一个很好的机会来更熟悉 Haskell 的类型系统和一般类型系统。 (所以我也不是在寻找其他人的实现。)
我的想法如下:我可以使用 GADTs 来 "tag" 一个列表,其中包含它可以应用的函数类型。因此,我重新定义 Nil
和 Cons
的方式与我们使用 Nat
定义对类型中的列表长度进行编码的方式类似,但不是使用 Peano 数字,而是以某种方式对长度进行编码在标记函数类型中(即长度对应于函数的参数数量)。
这是我目前的代码:
{-# LANGUAGE GADTs #-}
-- n represents structure of the function I apply to
-- o represents output type of the function
-- a represents argument type of the function (all arguments same type)
data FList n o a where
-- with Nil the function is the output
Nil :: FList o o a
-- with Cons the corresponding function takes one more argument
Cons :: a -> FList f o a -> FList (a -> f) o a
args0 = Nil :: FList Int Int Int -- will not apply an argument
args1 = Cons 1 args0 -- :: FList (Int -> Int) Int Int
args2 = Cons 2 args1 -- :: FList (Int -> Int -> Int) Int Int
args3 = Cons 3 args2 -- :: FList (Int -> Int -> Int -> Int) Int Int
listApply :: (n -> o) -> FList (n -> o) o a -> o
-- I match on (Cons p Nil) because I always want fun to be a function (n -> o)
listApply fun (Cons p Nil) = fun p
listApply fun (Cons p l) = listApply (fun p) l
main = print $ listApply (+) args2
在最后一行,我的想法是 (+)
将是 Int -> Int -> Int
类型,其中 Int -> Int
对应于 (n -> o)
中的 n
o
对应于最后一个 Int
(输出)[1]。据我所知,这种类型似乎适用于我的 argsN
定义的类型。
但是,我得到了两个错误,我将说明其中与我相关的部分:
test.hs:19:43:
Could not deduce (f ~ (n0 -> f))
from the context ((n -> o) ~ (a -> f))
bound by a pattern with constructor
Cons :: forall o a f. a -> FList f o a -> FList (a -> f) o a,
in an equation for ‘listApply’
和
test.hs:21:34:
Couldn't match type ‘Int’ with ‘Int -> Int’
Expected type: FList (Int -> Int -> Int) (Int -> Int) Int
Actual type: FList (Int -> Int -> Int) Int Int
In the second argument of ‘listApply’, namely ‘args2’
我不确定如何解释第一个错误。第二个错误让我感到困惑,因为它与我之前用 [1] 标记的解释不符。
对出了什么问题有任何见解吗?
P.S:我非常愿意了解新的扩展,如果可以的话。
你几乎答对了。递归应该遵循GADT的结构:
{-# LANGUAGE GADTs #-}
-- n represents structure of the function I apply to
-- o represents output type of the function
-- a represents argument type of the function (all arguments same type)
data FList n o a where
-- with Nil the function is the output
Nil :: FList o o a
-- with Cons the corresponding function takes one more argument
Cons :: a -> FList f o a -> FList (a -> f) o a
args0 = Nil :: FList Int Int Int -- will not apply an argument
args1 = Cons 1 args0 -- :: FList (Int -> Int) Int Int
args2 = Cons 2 args1 -- :: FList (Int -> Int -> Int) Int Int
args3 = Cons 3 args2 -- :: FList (Int -> Int -> Int -> Int) Int Int
-- n, not (n -> o)
listApply :: n -> FList n o a -> o
listApply fun Nil = fun
listApply fun (Cons p l) = listApply (fun p) l
main = print $ listApply (+) args2
three :: Int
three = listApply (+) (Cons 2 (Cons 1 Nil))
oof :: String
oof = listApply reverse (Cons "foo" Nil)
true :: Bool
true = listApply True Nil -- True
-- The return type can be different than the arguments:
showplus :: Int -> Int -> String
showplus x y = show (x + y)
zero :: String
zero = listApply showplus (Cons 2 (Cons 1 Nil))
不得不说,这看起来很优雅!
连OP都不要求别人实现。您可以稍微不同地处理问题,从而导致外观不同但整洁 API:
{-# LANGUAGE KindSignatures #-}
{-# LANGuAGE DataKinds #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
import Data.Proxy
data N = O | S N
p0 :: Proxy O
p1 :: Proxy (S O)
p2 :: Proxy (S (S O))
p0 = Proxy
p1 = Proxy
p2 = Proxy
type family ArityNFun (n :: N) (a :: *) (b :: *) where
ArityNFun O a b = b
ArityNFun (S n) a b = a -> ArityNFun n a b
listApply :: Proxy n -> ArityNFun n a b -> ArityNFun n a b
listApply _ = id
three :: Int
three = listApply p2 (+) 2 1
oof :: String
oof = listApply p1 reverse "foo"
true :: Bool
true = listApply p0 True
showplus :: Int -> Int -> String
showplus x y = show (x + y)
zero :: String
zero = listApply p2 showplus 0 0
这里我们可以使用 GHC.TypeLits
中的 Nat
,但之后我们需要 UndecidableInstances
。在这个例子中添加的糖是不值得的。
如果你想制作多态版本,那也是可以的,但是索引不是(n :: Nat) (a :: *)
而是(as :: [*])
。对于两种编码,制作 plusN
也是一个很好的练习。
不是一回事,但我怀疑您会对 free applicative functor, which the free
library 提供的内容感兴趣。它是这样的(基于 free
中的实现,但使用 :<**>
构造函数而不是 Ap
):
data Ap f a where
Pure :: a -> Ap f a
(:<**>) :: f x -> Ap f (x -> a) -> Ap f a
您可以将这些视为具有类型 f x0
、...、f xn
元素的异构类型列表,以 Pure (f :: x0 -> ... -> xn -> a)
终止。这就像一个用于应用计算的 "syntax tree",允许您使用常规的应用方法来构建一个 "tree",可以由解释器函数单独 运行。
练习: 实现以下实例:
instance Functor f => Functor (Ap f) where ...
instance Functor f => Applicative (Ap f) where ...
提示:Applicative
法律提供了一个方法,您可以使用它来实现这些。
作为练习,我正在尝试在 Haskell 中重新创建 Lisp 的 apply
。我不打算将它用于任何实际目的,我只是认为这是一个很好的机会来更熟悉 Haskell 的类型系统和一般类型系统。 (所以我也不是在寻找其他人的实现。)
我的想法如下:我可以使用 GADTs 来 "tag" 一个列表,其中包含它可以应用的函数类型。因此,我重新定义 Nil
和 Cons
的方式与我们使用 Nat
定义对类型中的列表长度进行编码的方式类似,但不是使用 Peano 数字,而是以某种方式对长度进行编码在标记函数类型中(即长度对应于函数的参数数量)。
这是我目前的代码:
{-# LANGUAGE GADTs #-}
-- n represents structure of the function I apply to
-- o represents output type of the function
-- a represents argument type of the function (all arguments same type)
data FList n o a where
-- with Nil the function is the output
Nil :: FList o o a
-- with Cons the corresponding function takes one more argument
Cons :: a -> FList f o a -> FList (a -> f) o a
args0 = Nil :: FList Int Int Int -- will not apply an argument
args1 = Cons 1 args0 -- :: FList (Int -> Int) Int Int
args2 = Cons 2 args1 -- :: FList (Int -> Int -> Int) Int Int
args3 = Cons 3 args2 -- :: FList (Int -> Int -> Int -> Int) Int Int
listApply :: (n -> o) -> FList (n -> o) o a -> o
-- I match on (Cons p Nil) because I always want fun to be a function (n -> o)
listApply fun (Cons p Nil) = fun p
listApply fun (Cons p l) = listApply (fun p) l
main = print $ listApply (+) args2
在最后一行,我的想法是 (+)
将是 Int -> Int -> Int
类型,其中 Int -> Int
对应于 (n -> o)
中的 n
o
对应于最后一个 Int
(输出)[1]。据我所知,这种类型似乎适用于我的 argsN
定义的类型。
但是,我得到了两个错误,我将说明其中与我相关的部分:
test.hs:19:43:
Could not deduce (f ~ (n0 -> f))
from the context ((n -> o) ~ (a -> f))
bound by a pattern with constructor
Cons :: forall o a f. a -> FList f o a -> FList (a -> f) o a,
in an equation for ‘listApply’
和
test.hs:21:34:
Couldn't match type ‘Int’ with ‘Int -> Int’
Expected type: FList (Int -> Int -> Int) (Int -> Int) Int
Actual type: FList (Int -> Int -> Int) Int Int
In the second argument of ‘listApply’, namely ‘args2’
我不确定如何解释第一个错误。第二个错误让我感到困惑,因为它与我之前用 [1] 标记的解释不符。
对出了什么问题有任何见解吗?
P.S:我非常愿意了解新的扩展,如果可以的话。
你几乎答对了。递归应该遵循GADT的结构:
{-# LANGUAGE GADTs #-}
-- n represents structure of the function I apply to
-- o represents output type of the function
-- a represents argument type of the function (all arguments same type)
data FList n o a where
-- with Nil the function is the output
Nil :: FList o o a
-- with Cons the corresponding function takes one more argument
Cons :: a -> FList f o a -> FList (a -> f) o a
args0 = Nil :: FList Int Int Int -- will not apply an argument
args1 = Cons 1 args0 -- :: FList (Int -> Int) Int Int
args2 = Cons 2 args1 -- :: FList (Int -> Int -> Int) Int Int
args3 = Cons 3 args2 -- :: FList (Int -> Int -> Int -> Int) Int Int
-- n, not (n -> o)
listApply :: n -> FList n o a -> o
listApply fun Nil = fun
listApply fun (Cons p l) = listApply (fun p) l
main = print $ listApply (+) args2
three :: Int
three = listApply (+) (Cons 2 (Cons 1 Nil))
oof :: String
oof = listApply reverse (Cons "foo" Nil)
true :: Bool
true = listApply True Nil -- True
-- The return type can be different than the arguments:
showplus :: Int -> Int -> String
showplus x y = show (x + y)
zero :: String
zero = listApply showplus (Cons 2 (Cons 1 Nil))
不得不说,这看起来很优雅!
连OP都不要求别人实现。您可以稍微不同地处理问题,从而导致外观不同但整洁 API:
{-# LANGUAGE KindSignatures #-}
{-# LANGuAGE DataKinds #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
import Data.Proxy
data N = O | S N
p0 :: Proxy O
p1 :: Proxy (S O)
p2 :: Proxy (S (S O))
p0 = Proxy
p1 = Proxy
p2 = Proxy
type family ArityNFun (n :: N) (a :: *) (b :: *) where
ArityNFun O a b = b
ArityNFun (S n) a b = a -> ArityNFun n a b
listApply :: Proxy n -> ArityNFun n a b -> ArityNFun n a b
listApply _ = id
three :: Int
three = listApply p2 (+) 2 1
oof :: String
oof = listApply p1 reverse "foo"
true :: Bool
true = listApply p0 True
showplus :: Int -> Int -> String
showplus x y = show (x + y)
zero :: String
zero = listApply p2 showplus 0 0
这里我们可以使用 GHC.TypeLits
中的 Nat
,但之后我们需要 UndecidableInstances
。在这个例子中添加的糖是不值得的。
如果你想制作多态版本,那也是可以的,但是索引不是(n :: Nat) (a :: *)
而是(as :: [*])
。对于两种编码,制作 plusN
也是一个很好的练习。
不是一回事,但我怀疑您会对 free applicative functor, which the free
library 提供的内容感兴趣。它是这样的(基于 free
中的实现,但使用 :<**>
构造函数而不是 Ap
):
data Ap f a where
Pure :: a -> Ap f a
(:<**>) :: f x -> Ap f (x -> a) -> Ap f a
您可以将这些视为具有类型 f x0
、...、f xn
元素的异构类型列表,以 Pure (f :: x0 -> ... -> xn -> a)
终止。这就像一个用于应用计算的 "syntax tree",允许您使用常规的应用方法来构建一个 "tree",可以由解释器函数单独 运行。
练习: 实现以下实例:
instance Functor f => Functor (Ap f) where ...
instance Functor f => Applicative (Ap f) where ...
提示:Applicative
法律提供了一个方法,您可以使用它来实现这些。