为什么在数据类型定义中编码函数？

Question

我发现很难在数据类型定义中获得关于编码函数的直觉.这是在State和IO类型的定义中完成的,例如

data State s a = State s -> (a,s)
type IO a = RealWorld -> (a, RealWorld) -- this is type synonym though, not new type

我想看一个更简单的例子来理解它的价值,所以我可以在此基础上建立更复杂的例子.例如,假设我有一个数据结构,那么在一个数据构造函数中编码函数是否有意义.

data Tree = Node Int (Tree) (Tree) (? -> ?) | E

我不确定我在这里尝试做什么,但是我可以在这种类型中编码的函数示例是什么？为什么我必须在类型中对其进行编码,但不要将其用作普通函数,我不知道,可能在需要时作为参数传递？

Answer 1

实际上,函数就像其他任何数据一样.

前奏>:I( - >)
data (->) a b -- Defined in`GHC.Prim '
instance Monad ((->) r) -- Defined in`GHC.Base'
instance Functor ((->) r) -- Defined in`GHC.Base"

如果您只考虑来自的功能,那么这很自然地出来并且没有任何概念上令人惊讶的事情Int.我会给他们一个奇怪的名字:( _{记住这(->) a b意味着a->b)}

type Array = (->) Int

什么？那么,阵列上最重要的操作是什么？

Prelude>:t(Data.Array.!)
(Data.Array.!):: GHC.Arr.Ix i => GHC.Arr.Array ie - > i - > e
Prelude>:t(Data.Vector.! )
(Data.Vector.!):: Data.Vector.Vector a - > Int - > a

让我们为自己的数组类型定义类似的东西:

(!) :: Array a -> Int -> a
(!) = ($)

现在我们可以做到

test :: Array String
test 0 = "bla"
test 1 = "foo"

FnArray>测试!0
"bla"
FnArray>测试!1
"foo"
FnArray>测试!2
"***异常:: 8:5-34:功能测试中的非详尽模式

比较这个

Prelude Data.Vector> let test = fromList ["bla","foo"]
Prelude Data.Vector> test!0
"bla"
Prelude Data.Vector> test!1
"foo"
Prelude Data.Vector> test!2
"***异常:./ Data/Vector/Generic.hs:244((!)):索引越界(2,2)

没有那么不同,对吗？这是Haskell对参照透明度的强制执行,它保证了函数的返回值实际上可以解释为某个容器的居民值.这是查看Functor实例的一种常用方法:fmap transform f将一些转换应用于"包含"的值f(作为结果值).这通过简单地在目标函数之后组成转换来工作:

instance Functor (r ->) where
  fmap transform f x = transform $ f x

(虽然你当然更好地写这个fmap = (.).)

现在,更令人困惑的是(->)类型构造函数还有一个类型参数:参数类型.让我们通过定义来关注它

{-# LANGUAGE TypeOperators #-}

newtype (:<-) a b = BackFunc (b->a)

要感受一下:

show' :: Show a  =>  String :<- a
show' = BackFunc show

即它实际上只是反过来写的功能箭头.

是(:<-) Int某种容器,(->) Int类似于数组的类似？不完全的.我们无法定义instance Functor (a :<-).然而,从数学上讲,它(a :<-) 是一种仿函数,但却是一种不同的类型:逆变仿函数.

instance Contravariant (a :<-) where
  contramap transform (BackFunc f) = BackFunc $ f . transform

"普通"仿函数OTOH是协变仿函数.如果直接比较,命名很容易理解:

fmap      :: Functor f       => (a->b) -> f a->f b
contramap :: Contravariant f => (b->a) -> f a->f b

虽然逆变函子并不像协变函数那样常用,但在推理数据流等时可以大致相同的方式使用它们.当在数据字段中使用函数时,它应该是你应该首先考虑的协变与逆变,不是函数与值 - 因为实际上,与纯函数式语言中的"静态值"相比,函数没有什么特别之处.

关于你的Tree类型

我不认为这种数据类型可以成为真正有用的东西,但是我们可以用类似的类型做一些愚蠢的事情,这可能说明我上面提出的观点:

data Tree' = Node Int (Bool -> Tree) | E

也就是说,对性能的反思,与通常的同构

data Tree = Node Int Tree Tree | E

为什么？嗯,Bool -> Tree类似于Array Tree,除了我们不使用Ints进行索引而是Bools.并且只有两个可评估的布尔值.固定大小为2的数组通常称为元组.并与Bool->Tree ? (Tree, Tree)我们有Node Int (Bool->Tree) ? Node Int Tree Tree.

不可否认,这并不是那么有趣.对于来自固定域的函数,同构通常是显而易见的.有趣的案例在函数域和/或codomain上是多态的,这总是会导致一些抽象的结果,例如状态monad.但即使在这些情况下,您也记得在Haskell中没有任何内容真正与其他数据类型分离.