더 높은 종류의 유형은 언제 유용합니까?

더 높은 종류의 유형은 언제 유용합니까?

---

나는 한동안 F #에서 개발을 해왔고 그것을 좋아합니다. 그러나 내가 아는 한 가지 유행어는 F #에 존재하지 않는 고급 유형입니다. 나는 고급 유형에 대한 자료를 읽었으며 그 정의를 이해한다고 생각합니다. 왜 그들이 유용한 지 잘 모르겠습니다. 누군가 Scala 또는 Haskell에서 F #의 해결 방법이 필요한 고급 유형의 예를 제공 할 수 있습니까? 또한 이러한 예제의 경우 더 높은 종류의 유형이 없으면 해결 방법은 무엇입니까 (또는 F #의 경우 그 반대)? 어쩌면 나는 그 문제를 해결하는 데 너무 익숙해서 그 기능이 없다는 것을 알지 못합니다.

(나는 생각한다) 대신 myList |> List.map f또는 myList |> Seq.map f |> Seq.toList더 높은 종류의 유형을 사용하면 간단하게 작성할 myList |> map f수 있으며 List. 훌륭하지만 (정확하다고 가정 할 때) 약간 사소한 것 같습니까? (그리고 단순히 함수 오버로딩을 허용하는 것만으로 할 수는 없습니까?) 저는 보통 Seq어쨌든 로 변환 한 다음 나중에 원하는대로 변환 할 수 있습니다. 다시 말하지만, 아마도 나는 그것을 해결하는 데 너무 익숙 할 것입니다. 그러나 더 높은 종류의 유형 이 키 입력이나 유형 안전에서 실제로 당신을 구하는 예가 있습니까?

---

따라서 유형의 종류는 단순한 유형입니다. 예를 들어 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에서 이것을 더 나아갈 수 있습니다. 예를 들어 우리는 kind를 가진 유형을 찾을 수 (* -> *) -> *있습니다. 이것의 간단한 예 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

하지만 분기 유형에 a Pairof 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유형 생성자에는 kind가 (* -> *) -> * -> *있습니다. 우리는 그것을 사용하여 다음과 같은 흥미로운 다른 변형을 만들 수 있습니다.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))

---

이것이 나타나는 또 다른 장소는 "펑터의 대수"입니다. 추상화 레이어를 몇 개 삭제하면 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)

---

그들은 이론적으로는 가능이야하지만 마지막으로, 나는 못 볼 것 도 높은 kinded 타입의 생성자를. 우리는 때때로.와 같은 유형의 함수를 볼 수 mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b있지만 유형의 복잡성 수준을 보려면 유형 프롤로그 또는 종속 유형 문서를 파헤쳐 야한다고 생각합니다.

---

더 높은 종류의 유형 변수가있는 FunctorHaskell 의 유형 클래스를 고려하십시오 f.

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

이 유형 서명이 말하는 것은 fmap이의 유형 매개 변수를 ffrom a으로 변경 b하지만 f그대로 유지한다는 것입니다. 따라서 fmap목록을 통해 사용 하면 목록을 얻을 수 있고 파서를 통해 사용하면 구문 분석기를 얻게되는 식입니다. 그리고 이것들은 정적 , 컴파일 타임 보장입니다.

저는 F #을 모릅니다.하지만 Functor상속과 제네릭을 사용하여 더 높은 종류의 제네릭이없는 Java 또는 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.

There are other, more complicated ways you can try, but none of them really works. For example, you could try augment the first try by defining subtypes of Functor that restrict the result type:

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);
}

// …

This helps to forbid implementers of those narrower interfaces from returning the wrong type of Functor from the map method, but since there is no limit to how many Functor implementations you can have, there is no limit to how many narrower interfaces you'll need.

(EDIT: And note that this only works because Functor<B> appears as the result type, and so the child interfaces can narrow it. So AFAIK we can't narrow both uses of Monad<B> in the following interface:

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

In Haskell, with higher-rank type variables, this is (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Yet another try is to use recursive generics to try and have the interface restrict the result type of the subtype to the subtype itself. Toy example:

/**
 * 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);

}

But this sort of technique (which is rather arcane to your run-of-the-mill OOP developer, heck to your run-of-the-mill functional developer as well) still can't express the desired Functor constraint either:

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

The problem here is this doesn't restrict FB to have the same F as FA—so that when you declare a type List<A> implements Functor<List<A>, A>, the map method can still return a NotAList<B> implements Functor<NotAList<B>, B>.

Final try, in Java, using raw types (unparametrized containers):

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

Here F will get instantiated to unparametrized types like just List or Map. This guarantees that a FunctorStrategy<List> can only return a List—but you've abandoned the use of type variables to track the element types of the lists.

The heart of the problem here is that languages like Java and C# don't allow type parameters to have parameters. In Java, if T is a type variable, you can write T and List<T>, but not T<String>. Higher-kinded types remove this restriction, so that you could have something like this (not fully thought out):

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) {
        // ...
    }

}

---

And addressing this bit in particular:

(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.

There are many languages that generalize the idea of the map function this way, by modeling it as if, at heart, mapping is about sequences. This remark of yours is in that spirit: if you have a type that supports conversion to and from Seq, you get the map operation "for free" by reusing Seq.map.

In Haskell, however, the Functor class is more general than that; it isn't tied to the notion of sequences. You can implement fmap for types that have no good mapping to sequences, like IO actions, parser combinators, functions, etc.:

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

The concept of "mapping" really isn't tied to sequences. It's best to understand the functor laws:

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

Very informally:

1. The first law says that mapping with an identity/noop function is the same as doing nothing.
2. The second law says that any result that you can produce by mapping twice, you can also produce by mapping once.

This is why you want fmap to preserve the type—because as soon as you get map operations that produce a different result type, it becomes much, much harder to make guarantees like this.

---

I don't want to repeat information in some excellent answers already here, but there's a key point I'd like to add.

You usually don't need higher-kinded types to implement any one particular monad, or functor (or applicative functor, or arrow, or ...). But doing so is mostly missing the point.

In general I've found that when people don't see the usefulness of functors/monads/whatevers, it's often because they're thinking of these things one at a time. Functor/monad/etc operations really add nothing to any one instance (instead of calling bind, fmap, etc I could just call whatever operations I used to implement bind, fmap, etc). What you really want these abstractions for is so you can have code that works generically with any functor/monad/etc.

In a context where such generic code is widely used, this means any time you write a new monad instance your type immediately gains access to a large number of useful operations that have already been written for you. That's the point of seeing monads (and functors, and ...) everywhere; not so that I can use bind rather than concat and map to implement myFunkyListOperation (which gains me nothing in itself), but rather so that when I come to need myFunkyParserOperation and myFunkyIOOperation I can re-use the code I originally saw in terms of lists because it's actually monad-generic.

But to abstract across a parameterised type like a monad with type safety, you need higher-kinded types (as well explained in other answers here).

---

For a more .NET-specific perspective, I wrote a blog post about this a while back. The crux of it is, with higher-kinded types, you could potentially reuse the same LINQ blocks between IEnumerables and IObservables, but without higher-kinded types this is impossible.

The closest you could get (I figured out after posting the blog) is to make your own IEnumerable<T> and IObservable<T> and extended them both from an IMonad<T>. This would allow you to reuse your LINQ blocks if they're denoted IMonad<T>, but then it's no longer typesafe because it allows you to mix-and-match IObservables and IEnumerables within the same block, which while it may sound intriguing to enable this, you'd basically just get some undefined behavior.

I wrote a later post on how Haskell makes this easy. (A no-op, really--restricting a block to a certain kind of monad requires code; enabling reuse is the default).

---

The most-used example of higher-kinded type polymorphism in Haskell is the Monad interface. Functor and Applicative are higher-kinded in the same way, so I'll show Functor in order to show something concise.

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

Now, examine that definition, looking at how the type variable f is used. You'll see that f can't mean a type that has value. You can identify values in that type signature because they're arguments to and results of a functions. So the type variables a and b are types that can have values. So are the type expressions f a and f b. But not f itself. f is an example of a higher-kinded type variable. Given that * is the kind of types that can have values, f must have the kind * -> *. That is, it takes a type that can have values, because we know from previous examination that a and b must have values. And we also know that f a and f b must have values, so it returns a type that must have values.

This makes the f used in the definition of Functor a higher-kinded type variable.

The Applicative and Monad interfaces add more, but they're compatible. This means that they work on type variables with kind * -> * as well.

Working on higher-kinded types introduces an additional level of abstraction - you aren't restricted to just creating abstractions over basic types. You can also create abstractions over types that modify other types.

참고URL : https://stackoverflow.com/questions/21170493/when-are-higher-kinded-types-useful