首页 文章

较高的kinded类型何时有用？

提问于
浏览 次
83

我一直在做F＃开发一段时间，我喜欢它 . 然而，我知道在F＃中不存在的一个流行语是更高级的类型 . 我已经阅读了关于高等类型的材料，我想我理解他们的定义 . 我只是不确定他们为什么有用 . 有人可以在Scala或Haskell中提供一些高级类型易于使用的示例吗？这需要F＃中的变通方法？同样对于这些示例，如果没有更高级的类型（或F＃中反之亦然），解决方法是什么？也许我只是习惯于解决它，我没有注意到这个功能的缺席 .

（我认为）我得到的不是 myList |> List.map f 或 myList |> Seq.map f |> Seq.toList 更高的kinded类型允许你简单地写 myList |> map f 并且它将返回 List . 那个's great (assuming it'是正确的），但似乎有点小气？ （并且不能简单地通过允许函数重载来完成？）我通常转换为 Seq 然后我可以转换为我想要的任何东西 . 再说一次，也许我只是习惯于解决它 . 但有没有任何一个例子，高级类型的类型真的可以节省你的击键或类型安全？

scala haskell types f# higher-kinded-types

5 回答

  • 60

    所以类型的类型是它的简单类型 . 例如 Int 有类 * ，这意味着它不确定F＃在哪里绘制线，所以让我们只包括它）多态容器是一个更好的类型的一个很好的例子 .

    data List a = Cons a (List a) | Nil

    类型构造函数 List 具有类型 * -> * ，这意味着它必须传递具体类型才能生成具体类型： List Int 可以拥有像 [1,2,3] 这样的居民，但 List 本身不能 .

    我将假设多态容器的好处是显而易见的，但存在更多有用的类型 * -> * 类型而不仅仅是容器 . 例如，关系

    data Rel a = Rel (a -> a -> Bool)

    或解析器

    data Parser a = Parser (String -> [(a, String)])

    两者也有点 * -> * .

    然而，我们可以在Haskell中进一步采用具有更高阶类型的类型 . 例如，我们可以查找类型 (* -> *) -> * 的类型 . 一个简单的例子可能是 Shape ，它试图填充 * -> * 类型的容器 .

    data Shape f = Shape (f ())

[(), (), ()] :: Shape List

    例如，这对于表征Haskell中的 Traversable 是很有用的，因为它们总是可以分为它们的形状和内容 .

    split :: Traversable t => t a -> (Shape t, [a])

    作为另一个例子，让我们考虑一个在它所具有的分支类型上参数化的树 . 例如，可能是普通树

    data Tree a = Branch (Tree a) a (Tree a) | Leaf

    但我们可以看到分支类型包含 Pair 的 Tree a s，因此我们可以参数化地从类型中提取该片段

    data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

    这个 TreeG 类型的构造函数有类 (* -> *) -> * -> * . 我们可以使用它来制作有趣的其他变体，如 RoseTree

    type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

    或病态的像 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))

    显示的另一个地方是"algebras of functors" . 如果我们放弃几层抽象，这可能更好地被视为折叠，例如 sum :: [Int] -> Int . 代数是在仿函数和载体上参数化的 . 仿函数 * -> * 和载体种类 * 完全如此

    data Alg f a = Alg (f a -> a)

    有点 (* -> *) -> * -> * . Alg 非常有用，因为它与数据类型和在它们之上构建的递归方案有关 .

    -- | 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 ，但我认为你必须深入研究类型序言或依赖类型的文献才能看到类型的复杂程度 .

    回复于
  • 14

    考虑Haskell中的 Functor 类型类，其中 f 是一个更高级的类型变量：

    class Functor f where
    fmap :: (a -> b) -> f a -> f b

    此类型签名所说的是fmap将 f 的类型参数从 a 更改为 b ，但保留 f . 因此，如果您在列表上使用 fmap ，则会获得一个列表，如果您在解析器上使用它，则会获得解析器，依此类推 . 这些是静态的编译时保证 .

    如果我们试图用Java或C＃这样的语言表达 Functor 抽象，继承和泛型，但没有更高级的泛型，我不会考虑会发生什么 . 第一次尝试：

    interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

    第一次尝试的问题是允许接口的实现返回实现 Functor 的任何类 . 有人可以写一个 FunnyList<A> implements Functor<A> ，其 map 方法返回一个不同类型的集合，甚至是其他根本不是集合但仍然是 Functor 的东西 . 此外，当您使用 map 方法时，您实际上可以期待't invoke any subtype-specific methods on the result unless you downcast it to the type that you' . 所以我们有两个问题：

    • 类型系统不允许我们表达 map 方法总是返回与接收者相同的 Functor 子类的不变量 .

    • 因此，在 map 的结果上调用非 Functor 方法没有静态类型安全的方式 .

    您可以尝试其他更复杂的方法，但它们都不起作用 . 例如，您可以尝试通过定义限制结果类型的 Functor 的子类型来扩充第一次尝试：

    interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

    这有助于禁止那些较窄接口的实现者从 map 方法返回错误类型的 Functor ，但由于您可以拥有多少 Functor 实现，因此您需要的接口数量没有限制 .

    （ EDIT: 请注意，这只有效，因为 Functor<B> 显示为结果类型，因此子接口可以缩小它 . 所以AFAIK我们不能缩小以下界面中 Monad<B> 的两种用法：

    interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

    在Haskell中，具有更高级别的类型变量，这是 (>>=) :: Monad m => m a -> (a -> m b) -> m b . ）

    另一种尝试是使用递归泛型来尝试使接口将子类型的结果类型限制为子类型本身 . 玩具示例：

    /**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

    但是这种技术（对你的普通OOP开发人员来说相当骇人听闻，对你们普通的功能开发人员而言）仍然无法表达所需的 Functor 约束：

    interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

    这里的问题是，这并不限制 FB 与 FA 具有相同的 F ，因此当您声明类型 List<A> implements Functor<List<A>, A> 时， map 方法可以 still 返回 NotAList<B> implements Functor<NotAList<B>, B> .

    Java中的最终尝试，使用原始类型（非参数化容器）：

    interface FunctorStrategy<F> {
    F map(Function f, F arg);
}

    这里 F 将被实例化为非参数类型，例如 List 或 Map . 这可以保证 FunctorStrategy<List> 只能返回 List - 但是您已经放弃使用类型变量来跟踪列表的元素类型 .

    这里问题的核心是Java和C＃等语言不允许类型参数具有参数 . 在Java中，如果 T 是类型变量，则可以编写 T 和 List<T> ，但不能编写 T<String> . 较高级别的类型会删除此限制，因此您可以使用此类内容（未完全考虑）：

    interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

    并特别解决了这个问题：

    （我认为）我得到的不是myList |> List.map f或myList |> Seq.map f |> Seq.toList更高级的kinded类型允许你简单地写myList |> map f它会返回一个List . 这很好（假设它是正确的），但似乎有点小？ （并且不能简单地通过允许函数重载来完成？）我通常转换为Seq然后我可以转换为我想要的任何东西 .

    有许多语言通过这种方式概括了 map 函数的概念，通过对其进行建模，就像在心脏上映射是关于序列一样 . 你的这句话就是那种精神：如果你有一个支持从 Seq 转换的类型，你可以通过重用 Seq.map 获得 Map 操作"for free" .

    然而，在Haskell中， Functor 类比这更普遍;它与序列的概念无关 . 您可以为没有良好映射到序列的类型实现 fmap ，例如 IO actions，parser combinators，functions等：

    instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

    “映射”的概念实际上并不依赖于序列 . 最好理解仿函数法则：

    (1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

    非正式地：

    • 第一定律说用身份/ noop函数进行映射与什么都不做是一样的 .

    • 第二定律说你可以通过映射两次产生的任何结果，你也可以通过映射产生一次 .

    这就是为什么你希望 fmap 保留类型的原因 - 因为只要你得到产生不同结果类型的 map 操作，就会变得更加困难，这样做很难 .

    回复于
  • 13

    我不想在这里的一些优秀答案中重复信息，但我想补充一点 .

    您通常不需要更高级的类型来实现任何一个特定的monad，或functor（或applicative functor，或arrow，或......） . 但这样做大多是错过了重点 .

    一般来说，我看到了仿函数/ monads / whatevers的用处，它一次只能想到这些东西 . Functor / monad / etc操作真的没有添加任何一个实例（而不是调用bind，fmap等我可以调用我用来实现bind，fmap等的任何操作） . 你真正想要的这些抽象是因为你可以拥有与 any functor / monad / etc一般工作的代码 .

    在这种通用代码被广泛使用的上下文中，这意味着无论何时编写新的monad实例，您的类型都会立即获得对大量有用操作的访问权限 that have already been written for you . 这就是到处看monad（和functor，......）的重点;不是因为我可以使用 bind 而不是 concat 和 map 来实现 myFunkyListOperation （它本身没有任何收获），而是当我需要 myFunkyParserOperation 和 myFunkyIOOperation 时，我可以重新使用我最初在列表方面看到的代码因为它实际上是monad-generic .

    但是要在类型安全的monad之类的参数化类型中进行抽象，你需要更高级的类型（在此处的其他答案中也有解释） .

    回复于
  • 75

    对于更具特定于.NET的观点，我前段时间写了一篇关于这个问题的文章blog post . 它的关键在于，使用更高级别的类型，您可以在 IEnumerables 和 IObservables 之间重复使用相同的LINQ块，但是如果没有更高级的类型，这是不可能的 .

    你可以得到的最接近的（我发布博客后想出来的）是制作你自己的 IEnumerable<T> 和 IObservable<T> 并将它们从 IMonad<T> 扩展 . 如果它们被表示为 IMonad<T> ，这将允许您重用LINQ块，但它不再是类型安全的，因为它允许您在同一个块中混合并匹配 IObservables 和 IEnumerables ，虽然它可能听起来很有趣，但是，你基本上只是得到一些未定义的行为 .

    我写了一篇关于Haskell如何让这个变得容易的later post . （无操作，真的 - 将块限制为某种monad需要代码;启用重用是默认设置） .

    回复于
  • 26

    Haskell中最常用的高级类型多态性的例子是 Monad 接口 . Functor 和 Applicative 以同样的方式进行了更高的交易，因此我将展示 Functor 以显示简洁的内容 .

    class Functor f where
    fmap :: (a -> b) -> f a -> f b

    现在，检查该定义，查看如何使用类型变量 f . 你会看到 f 可以't mean a type that has value. You can identify values in that type signature because they'重新参数和函数的结果 . 因此类型变量 a 和 b 是可以具有值的类型 . 类型表达式 f a 和 f b 也是如此 . 但不是 f 本身 . f 是高级类型变量的示例 . 鉴于 * 是可以具有值的类型， f 必须具有 * -> * 类型 . 也就是说，它需要一个可以具有值的类型，因为我们从之前的检查中知道 a 和 b 必须具有值 . 并且我们也知道 f a 和 f b 必须具有值，因此它返回必须具有值的类型 .

    这使 f 在 Functor 的定义中使用了更高的类型变量 .

    Applicative 和 Monad 接口添加更多，但它们兼容 . 这意味着它们也可以使用类型 * -> * 处理类型变量 .

    处理更高级别的类型引入了额外的抽象级别 - 您不仅限于创建基本类型的抽象 . 您还可以在修改其他类型的类型上创建抽象 .

    回复于

相关问题