什么时候更高的亲属类型有用? [英] When are higher kinded types useful?
问题描述
我已经在F#开发了一段时间了,我喜欢它。但是我知道F#中不存在的一个流行词是高级类型。我已经阅读了更高版本的材料,我想我理解他们的定义。我只是不确定他们为什么有用。有人可以提供一些例子,说明在Scala或Haskell中哪些高级类型变得容易,需要F#中的解决方法?同样对于这些例子,如果没有更高版本的类型(或者反过来在F#中),这种解决方法是什么?也许我只是习惯于解决它,我没有注意到该功能的缺失。
I've been doing dev in F# for a while and I like it. However one buzzword I know doesn't exist in F# is higher-kinded types. I've read material on higher-kinded types, and I think I understand their definition. I'm just not sure why they're useful. Can someone provide some examples of what higher-kinded types make easy in Scala or Haskell, that require workarounds in F#? Also for these examples, what would the workarounds be without higher-kinded types (or vice-versa in F#)? Maybe I'm just so used to working around it that I don't notice the absence of that feature.
(我认为)我得到的不是 myList |> List.map f
或 myList |> Seq.map f |> Seq.toList
更高版本的类型允许您简单地编写 myList |> map f
,它会返回一个 List
。这很好(假设它是正确的),但似乎有点小气? (并不能简单地通过允许函数重载来完成?)我通常转换为 Seq
,然后我可以转换为任何我想要的东西。再次,也许我太习惯于解决它了。但是有没有什么例子可以让更高级别的类型真的能够在键盘输入或类型安全中为你节省?
(I think) I get that instead of myList |> List.map f
or myList |> Seq.map f |> Seq.toList
higher kinded types allow you to simply write myList |> map f
and it'll return a List
. That's great (assuming it's correct), but seems kind of petty? (And couldn't it be done simply by allowing function overloading?) I usually convert to Seq
anyway and then I can convert to whatever I want afterwards. Again, maybe I'm just too used to working around it. But is there any example where higher-kinded types really saves you either in keystrokes or in type safety?
推荐答案
所以这种类型是它的简单类型。例如 Int
有类型 *
,这意味着它是一个基本类型,可以通过值实例化。通过一些较高版本类型的松散定义(我不确定F#在哪里画线,所以让我们把它包括进来)。多态容器是一个更高接口类型的好例子。 p>
So the kind of a type is its simple type. For instance Int
has kind *
which means it's a base type and can be instantiated by values. By some loose definition of higher-kinded type (and I'm not sure where F# draws the line, so let's just include it) polymorphic containers are a great example of a higher-kinded type.
data List a = Cons a (List a) | Nil
类型构造函数 List
code> * - > * 这意味着它必须传递一个具体类型才能生成具体类型: List Int
可以有像 [1,2,3]
但
The type constructor List
has kind * -> *
which means that it must be passed a concrete type in order to result in a concrete type: List Int
can have inhabitants like [1,2,3]
but List
itself cannot.
I我们将假设多态容器的好处是显而易见的,但更有用的类型 * - > *
类型不仅仅是容器。例如,关系
I'm going to assume that the benefits of polymorphic containers are obvious, but more useful kind * -> *
types exist than just the containers. For instance, the relations
data Rel a = Rel (a -> a -> Bool)
或解析器
data Parser a = Parser (String -> [(a, String)])
kind * - > *
。
然而,我们可以在Haskell中进一步研究,更高阶的种类。例如,我们可以寻找类型为(* - > *) - >的类型。 *
。一个简单的例子可能是 Shape
,它试图填充一个类型为 * - >的容器。 *
。
We can take this further in Haskell, however, by having types with even higher-order kinds. For instance we could look for a type with kind (* -> *) -> *
. A simple example of this might be Shape
which tries to fill a container of kind * -> *
.
data Shape f = Shape (f ())
[(), (), ()] :: Shape List
例如code> Traversable ,因为它们总是可以分成它们的形状和内容。
This is useful for characterizing Traversable
s in Haskell, for instance, as they can always be divided into their shape and contents.
split :: Traversable t => t a -> (Shape t, [a])
例如,让我们考虑一个在它所拥有的分支上进行参数化的树。例如,一棵正常的树可能是
As another example, let's consider a tree that's parameterized on the kind of branch it has. For instance, a normal tree might be
data Tree a = Branch (Tree a) a (Tree a) | Leaf
但我们可以看到分支类型包含 Pair
树a
s,所以我们可以从参数类型中提取出该类型的元素
But we can see that the branch type contains a Pair
of Tree a
s and so we can extract that piece out of the type parametrically
data TreeG f a = Branch a (f (TreeG f a)) | Leaf
data Pair a = Pair a a
type Tree a = TreeG Pair a
这个 TreeG
类型构造函数有kind (* - > *) - > * - > *
。我们可以用它来制作有趣的其他变体,比如 RoseTree
This TreeG
type constructor has kind (* -> *) -> * -> *
. We can use it to make interesting other variations like a RoseTree
type RoseTree a = TreeG [] a
rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]
Or pathological ones like a MaybeTree
data Empty a = Empty
type MaybeTree a = TreeG Empty a
nothing :: MaybeTree a
nothing = Leaf
just :: a -> MaybeTree a
just a = Branch a Empty
或者 TreeTree
type TreeTree a = TreeG Tree a
treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))
显示的另一个地方是函子的代数。如果我们放弃几层抽象,这可能更好地被认为是一个折叠,例如 sum :: [Int] - > INT
。代数通过函子和载体进行参数化。 函子具有 * - > *
和承运人类别 *
所以一共
Another place this shows up is in "algebras of functors". If we drop a few layers of abstractness this might be better considered as a fold, such as sum :: [Int] -> Int
. Algebras are parameterized over the functor and the carrier. The functor has kind * -> *
and the carrier kind *
so altogether
data Alg f a = Alg (f a -> a)
has kind (* - > *) - > * - > *
。 Alg
有用,因为它与数据类型以及在它们上面构建的递归方案的关系。
has kind (* -> *) -> * -> *
. Alg
useful because of its relation to datatypes and recursion schemes built atop them.
-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
| Add x x
| Sub x x
| Mult x x
-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))
type Exp = Fix ExpF
exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4
fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)
最后,尽管它们在理论上是可行的,但我从来没有见过甚至更高级别的构造函数。我们有时会看到这种类型的函数,例如 mask ::((forall a。IO a - > IO a) - > IO b) - > IO b
,但我认为您必须深入研究类型序言或依赖类型的文献,以查看类型复杂程度。
Finally, though they're theoretically possible, I've never see an even higher-kinded type constructor. We sometimes see functions of that type such as mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b
, but I think you'll have to dig into type prolog or dependently typed literature to see that level of complexity in types.
这篇关于什么时候更高的亲属类型有用?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!