较高的kinded类型何时有用？

Question

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

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

Answer 1

所以类型的类型是它的简单类型.例如Int,kind *表示它是一个基类型,可以通过值实例化.通过对高级类型的一些宽松定义(我不确定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

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

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

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

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

但是我们可以看到该分支类型包含Pair的Tree aS和这样我们就可以提取出片的类型的参

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

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

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

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

或者a TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

这个出现的另一个地方是"算子的代数".如果我们放弃几层抽象,这可能更好地被视为折叠,例如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,但是我认为你必须深入研究类型序言或依赖类型的文献才能看到类型的复杂程度.

Answer 2

考虑FunctorHaskell中的类型类,其中f是一个更高级的类型变量:

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

这是什么类型的签名说的是,FMAP改变的类型参数f从a到b,但保留f原样.因此,如果您使用fmap列表,则会获得一个列表,如果您在解析器上使用它,则会获得解析器,依此类推.这些是静态的编译时保证.

我不知道F#,但让我们考虑如果我们试图用FunctorJava或C#这样的语言表达抽象,继承和泛型,但没有更高级的泛型.第一次尝试:

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

第一次尝试的问题是允许接口的实现返回任何实现的类Functor.有人可以写一个FunnyList<A> implements Functor<A>,其map方法都返回不同类型的集合,甚至是别的东西,这不是一个集合,但仍然是一个Functor.此外,当您使用该map方法时,您无法在结果上调用任何特定于子类型的方法,除非您将其向下转换为您实际期望的类型.所以我们有两个问题:

1. 类型系统不允许我们表示该map方法总是返回与Functor接收者相同的子类的不变量.
2. 因此,没有静态类型安全的方式来调用非Functor结果的方法map.

您可以尝试其他更复杂的方法,但它们都不起作用.例如,您可以尝试通过定义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);
}

// …

这有助于从返回错误类型的禁止那些窄接口的实施者Functor与map方法,但由于没有限制多少Functor你可以实现有,没有限制,你会多少较窄的接口需要.

(编辑:请注意,这只会起作用,因为它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具有相同F的FA-所以,当你声明一个类型List<A> implements Functor<List<A>, A>,该map方法能仍返回NotAList<B> implements Functor<NotAList<B>, B>.

Java中的最终尝试,使用原始类型(非参数化容器):

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

这里F将实例化为非参数类型,如just List或Map.这保证了a 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.

然而,在Haskell中,这个Functor类比这更普遍; 它与序列的概念无关.您可以实现fmap对序列没有良好映射的类型,例如IO操作,解析器组合器,函数等:

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

非正式地:

1. 第一条法则规定,使用身份/ noop功能进行映射与无所事事相同.
2. 第二定律说你可以通过映射两次产生的任何结果,你也可以通过映射产生一次.

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

Answer 3

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

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

一般来说,我发现,当人们看不到的仿函数/单子/凡是的实用性,它往往是因为他们在想这些东西一次一个.Functor/monad/etc操作实际上没有添加任何一个实例(而不是调用bind,fmap等我可以调用我用来实现 bind,fmap等的任何操作).你真正想要的这些抽象是因为你可以拥有与任何 functor/monad /等一般工作的代码.

在这种通用代码被广泛使用的上下文中,这意味着无论何时编写新的monad实例,您的类型都会立即获得对已经为您编写的大量有用操作的访问权限.这就是到处看monad(和functor,......)的重点; 并非如此,我可以使用bind,而不是concat与map实现myFunkyListOperation(其获得我什么本身),而是让我来的时候需要myFunkyParserOperation和myFunkyIOOperation我可以重复使用我原来在名单的角度来看待的代码,因为它实际上是单子泛型.

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

Answer 4

对于更具体的.NET视角,我前段时间写了一篇关于此的博客文章.它的关键在于,使用更高级别的类型,您可以在IEnumerables和之间重用相同的LINQ块IObservables,但是如果没有更高级的类型,这是不可能的.

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

我后来写了一篇关于Haskell如何简化这篇文章的文章.(无操作,真的 - 将块限制为某种monad需要代码;启用重用是默认设置).

Answer 5

Haskell中最常用的高级类型多态的例子是Monad接口.Functor并且Applicative以同样的方式获得更高的知名度,因此我将展示Functor以展示简洁的东西.

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

现在,检查该定义,查看类型变量f的使用方式.你会发现这f并不意味着一种有价值的类型.您可以识别该类型签名中的值,因为它们是函数的参数和结果.所以类型变量a和b类型都可以有值.类型表达式f a也是如此f b.但不是f自己. f是一个高级类型变量的例子.鉴于*那种可以拥有价值的类型,f必须有类型* -> *.也就是说,它需要一种可以具有值的类型,因为我们从之前的检查中知道a并且b必须具有值.我们也知道f a并且f b必须有值,因此它返回一个必须具有值的类型.

这使得f用于定义Functor更高通道的类型变量.

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

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