haskell - カレー商品の種類

Question

型ファミリを使用して、関数と定数値のnタプルとして表される型とその型の基礎となる代数の関数折り畳みを定義できます。これにより、Foldable型クラスで定義される一般化されたfoldr関数の定義が可能になります。

import Data.Set (Set)
import Data.Map (Map)
import qualified Data.Set as S
import qualified Data.Map as M

class Foldable m where
  type Algebra m b :: *
  fold :: Algebra m b -> m -> b

instance (Ord a) => Foldable (Set a) where
  type Algebra (Set a) b = (b, a -> b -> b)
  fold = uncurry $ flip S.fold

instance (Ord k) => Foldable (Map k a) where
  type Algebra (Map k a) b = (b, k -> a -> b -> b)
  fold = uncurry $ flip M.foldWithKey

同様に、制約の種類によって、一般化されたマップ関数を定義できます。map関数は、代数データ型の各値フィールドを考慮する点でfmapとは異なります。

class Mappable m where
  type Contains m     :: *
  type Mapped   m r b :: Constraint
  map :: (Mapped m r b) => (Contains m -> b) -> m -> r

instance (Ord a) => Mappable (Set a) where
  type Contains (Set a)     = a
  type Mapped   (Set a) r b = (Ord b, r ~ Set b)
  map = S.map

instance (Ord k) => Mappable (Map k a) where
  type Contains (Map k a)     = (k, a)
  type Mapped   (Map k a) r b = (Ord k, r ~ Map k b)
  map = M.mapWithKey . curry

ユーザーの観点からは、どちらの機能も特に使いやすいものではありません。特に、どちらの手法もカリー化された関数の定義を許可しません。これは、ユーザーがフォールドまたはマップされた関数を部分的に簡単に適用できないことを意味します。私が望むのは、上記のカリー化されたバージョンを生成するために、関数と値のタプルをカリー化する型レベルの関数です。したがって、次の型関数に近いものを書きたいと思います。

Curry :: Product -> Type -> Type
Curry ()       m = m
Curry (a × as) m = a -> (Curry as m b)

もしそうなら、基になる代数からカリー化された折り畳み関数を生成できます。例えば：

  fold :: Curry (Algebra [a] b) ([a] -> b)
≡ fold :: Curry (b, a -> b -> b) ([a] -> b)
≡ fold :: b -> (Curry (a -> b -> b)) ([a] -> b)
≡ fold :: b -> (a -> b -> b -> (Curry () ([a] -> b))
≡ fold :: b -> ((a -> b -> b) -> ([a] -> b))

  map :: (Mapped (Map k a) r b) => (Curry (Contains (Map k a)) b) -> Map k a -> r
≡ map :: (Mapped (Map k a) r b) => (Curry (k, a) b) -> Map k a -> r
≡ map :: (Mapped (Map k a) r b) => (k -> (Curry (a) b) -> Map k a -> r
≡ map :: (Mapped (Map k a) r b) => (k -> (a -> Curry () b)) -> Map k a -> r
≡ map :: (Mapped (Map k a) r b) => (k -> (a -> b)) -> Map k a -> r

Haskell には型関数がないことを私は知っています。nタプルの適切な表現は、おそらく型レベルの長さインデックス付きの型のリストのようなものでしょう。これは可能ですか？

編集:完全を期すために、解決策に対する私の現在の試みを以下に添付します。上記の型の積を表すために空のデータ型を使用し、関数Curryを表すために型ファミリを使用しています。このソリューションはmap関数では機能するように見えますが、fold関数では機能しません。型チェック時にCurryが適切に削減されていないことは確かではありませんが、私は信じています。

data Unit
data Times a b

type family Curry a m :: *
type instance Curry Unit        m = m
type instance Curry (Times a l) m = a -> Curry l m

class Foldable m where
  type Algebra m b :: *
  fold :: Curry (Algebra m b) (m -> b)

instance (Ord a) => Foldable (Set a) where
  type Algebra (Set a) b = Times (a -> b -> b) (Times b Unit)
  fold = S.fold

instance (Ord k) => Foldable (Map k a) where
  type Algebra (Map k a) b = Times (k -> a -> b -> b) (Times b Unit)
  fold = M.foldWithKey

 class Mappable m where
   type Contains m     :: *
   type Mapped   m r b :: Constraint
   map :: (Mapped m r b) => Curry (Contains m) b -> m -> r

 instance (Ord a) => Mappable (Set a) where
   type Contains (Set a)     = Times a Unit
   type Mapped   (Set a) r b = (Ord b, r ~ Set b)
   map = S.map

 instance (Ord k) => Mappable (Map k a) where
   type Contains (Map k a)     = Times k (Times a Unit)
   type Mapped   (Map k a) r b = (Ord k, r ~ Map k b)
   map = M.mapWithKey

Answer 1

わかりました、私があなたを正しく理解しているなら、あなたは不便な折り目を作ることができますが、便利なカリー化された折り目をしたい.

以下は、別のステップとしてこれを達成する方法の説明です。はい、一度に行うこともできます。以前に似たようなことをしたことがあります。ただし、別のフェーズにすることで、何が起こっているのかが明確になると思います。

次の言語拡張が必要です。

{-# LANGUAGE TypeFamilies, TypeOperators, FlexibleInstances #-}

次の製品とユニット タイプを使用しています。

data U = U
data a :*: b = a :*: b

infixr 8 :*:

例として、リストの折り畳みの不便なバージョンがあると仮定しましょう:

type ListAlgType a r = (U -> r)
                   :*: (a :*: r :*: U -> r)
                   :*: U

inconvenientFold :: ListAlgType a r -> [a] -> r
inconvenientFold   (nil :*: cons :*: U) []       = nil U
inconvenientFold a@(nil :*: cons :*: U) (x : xs) = cons (x :*: inconvenientFold a xs :*: U)

ネストされた製品タイプがあり、両方のレベルをカリー化したいと考えています。このために、レイヤーごとに 1 つずつ、2 つの型クラスを定義しています。（もう1つの一般的な機能で実行できるかもしれませんが、この場合は試していません。）

class CurryInner a where
  type CurryI a k :: *
  curryI   :: (a -> b) -> CurryI a b
  uncurryI :: CurryI a b -> a -> b

class CurryOuter a where
  type CurryO a k :: *
  curryO   :: (a -> b) -> CurryO a b
  uncurryO :: CurryO a b -> (a -> b) -- not really required here

各型クラスは、カリー化された型とカリー化されていない型の間の同形を実装します。型クラスは同じように見えますが、外側のネストされたタプルの各コンポーネントをCurryOuter呼び出します。CurryInner

インスタンスは比較的単純です。

instance CurryInner U where
  type CurryI U k = k
  curryI f   = f U
  uncurryI x = \ U -> x

instance CurryInner ts => CurryInner (t :*: ts) where
  type CurryI (t :*: ts) k = t -> CurryI ts k
  curryI f   = \ t -> curryI (\ ts -> f (t :*: ts))
  uncurryI f = \ (t :*: ts) -> uncurryI (f t) ts

instance CurryOuter U where
  type CurryO U k = k
  curryO f   = f U
  uncurryO x = \ U -> x

instance (CurryInner a, CurryOuter ts) => CurryOuter ((a -> b) :*: ts) where
  type CurryO ((a -> b) :*: ts) k = CurryI a b -> CurryO ts k
  curryO f   = \ t -> curryO (\ ts -> f (uncurryI t :*: ts))
  uncurryO f = \ (t :*: ts) -> uncurryO (f (curryI t)) ts

それでおしまい。ご了承ください

*Main> :kind! CurryO (ListAlgType A R) ([A] -> R)
CurryO (ListAlgType A R) ([A] -> R) :: *
= R -> (A -> R -> R) -> [A] -> R

(適切に定義されたプレースホルダ タイプAおよび の場合R)。次のように使用できます。

*Main> curryO inconvenientFold 0 (+) [1..10]
55

編集：あなたは実際には外側の層のカリー化についてのみ尋ねていることがわかりました。必要なクラスは 1 つだけですが、同じ考え方を使用できます。この例を使用したのは、以前に 2 レベルのカリー化を必要とする積和ベースのジェネリック プログラミング ライブラリ用に何かを書いたことがあり、最初は同じ設定にいると思ったからです。

Answer 2

わかりました。他の答えは、実際にはあなたの質問に対する答えではないと思います。そのために残念。

最終的なコードで、とのタイプを比較しfoldますmap。

fold :: Curry (Algebra m b) (m -> b)
map  :: (Mapped m r b) => Curry (Contains m) b -> m -> r

ここには大きな違いがあります。の型foldは単なる型族アプリケーションですが、の型にはクラスパラメータに言及するmapfinalが含まれています。したがって、の場合、GHCは、コンテキストからクラスをインスタンス化するタイプを簡単に知ることができます。m -> rmmap

fold残念ながら、型族は単射である必要がないため、逆にするのは簡単ではないため、そうではありません。したがって、使用foldしている特定のタイプを確認することによって、GHCが何であるかを推測することは不可能mです。

この問題の標準的な解決策は、次のようmに定義することにより、のタイプを修正するプロキシ引数を使用することです。

data Proxy m = P

fold代わりにこのタイプを指定します。

fold :: Proxy m -> Curry (Algebra m b) (m -> b)

プロキシ引数を取得して破棄するには、インスタンスを調整する必要があります。次に、次を使用できます。

fold (P :: Proxy (Set Int)) (+) 0 (S.fromList [1..10])

または、セットでfold関数を呼び出すのと同様です。

GHCがこの状況を解決するのが難しい理由をより明確に理解するには、代わりにこのおもちゃの例を検討してください。

class C a where
  type F a :: *
  f :: F a

instance C Bool where
  type F Bool = Char -> Char
  f = id

instance C () where
  type F () = Char -> Char
  f = toUpper

さて、あなたが電話f 'x'した場合、GHCがあなたが意図したインスタンスを検出するための意味のある方法はありません。プロキシはここでも役立ちます。

Answer 3

タイプレベルのリストはまさにあなたが必要とするものです！あなたは非常に接近しました、しかしあなたは両方の完全な力を必要とします、DataKindsそしてScopedTypeVariablesこれが正しく働くために：

{-# LANGUAGE ConstraintKinds, DataKinds, FlexibleContexts, FlexibleInstances, TypeFamilies, TypeOperators, ScopedTypeVariables #-}
import GHC.Exts (Constraint)
import Data.Set (Set)
import Data.Map (Map)
import qualified Data.Set as S
import qualified Data.Map as M

-- | A "multifunction" from a list of inhabitable types to an inhabitable type (curried from the start).  
type family (->>) (l :: [*]) (y :: *) :: *
type instance '[] ->> y = y
type instance (x ': xs) ->> y = x -> (xs ->> y)

class Foldable (m :: *) where
  type Algebra m (b :: *) :: [*]
  fold :: forall (b :: *). Algebra m b ->> (m -> b)

instance (Ord a) => Foldable (Set a) where
  type Algebra (Set a) b = '[(a -> b -> b), b]
  fold = S.fold :: forall (b :: *). (a -> b -> b) -> b -> Set a -> b

instance (Ord k) => Foldable (Map k a) where
  type Algebra (Map k a) b = '[(k -> a -> b -> b), b]
  fold = M.foldWithKey :: forall (b :: *). (k -> a -> b -> b) -> b -> Map k a -> b

class Mappable m where
  type Contains m :: [*]
  type Mapped m (b :: *) (r :: *) :: Constraint
  map :: forall (b :: *) (r :: *). Mapped m b r => (Contains m ->> b) -> m -> r

instance (Ord a) => Mappable (Set a) where
  type Contains (Set a) = '[a]
  type Mapped (Set a) b r = (Ord b, r ~ Set b)
  map = S.map :: forall (b :: *). (Ord b) => (a -> b) -> Set a -> Set b

instance (Ord k) => Mappable (Map k a) where
  type Contains (Map k a) = '[k, a]
  type Mapped (Map k a) b r = r ~ Map k b
  map = M.mapWithKey :: forall (b :: *). (k -> a -> b) -> Map k a -> Map k b