入れ子リストをサポートする "zipWith"がオーバーロードされました

Question

J languageで算術演算がどのように動作するかを、リストにバイナリ演算を自動的に分配するHaskell関数を記述しようとしています。 これは、深さのネストされたリストで動作する「深いzipWith」と考えることができます（非リストや異なる深度のリストを含む）。たとえば ：異なる長さの

distr (+) 1 10 === 11 -- Non-list values are added together 
distr (+) [1,2] 10 === [11,12] -- Non-list values distribute over lists 
distr (+) [1,2] [10,20] === [11,22] -- Two lists get zipped 
distr (+) [[1,2],[3,4]] [[10,20],[30,40]] === [[11,22],[33,44]] -- Nested lists get zipped 

リストはzipWithと同じように、切り捨てられ得るが、これは重要ではありません。

さて、私はすでにこれを書いた：

{-# LANGUAGE 
    MultiParamTypeClasses, 
    FunctionalDependencies, 
    UndecidableInstances, 
    FlexibleInstances 
#-} 

class Distr a b c x y z | a b c x y -> z 
    where distr :: (a -> b -> c) -> (x -> y -> z) 

instance Distr a b c a b c where distr = id 
instance {-# OVERLAPPING #-} 
     (Distr a b c x y z) => Distr a b c [x] [y] [z] 
    where distr = zipWith . distr 
instance (Distr a b c x y z) => Distr a b c [x] y [z] 
    where distr f xs y = map (\x -> distr f x y) xs 
instance (Distr a b c x y z) => Distr a b c x [y] [z] 
    where distr f x ys = map (\y -> distr f x y) ys 

これは、関数distr :: (Distr a b c x y z) => (a -> b -> c) -> (x -> y -> z)、およびネストされたリスト上のDistrのいくつかの事例で6パラメータの型クラスDistrを定義します。 これは上の例でうまくいきますが、不等ネスト深度のリスト上での振る舞いは、正確には私が望むものではありません。 それは、この（あなたが(+)に型注釈を追加し、両方のリストならば働く）を行います。私が欲しいもの

distr (+) [[1,2],[3,4]] [10,20] === [[11,12],[23,24]] -- Zip and distribute 

Try it here. はこれです：

distr (+) [[1,2],[3,4]] [10,20] === [[11,22],[13,24]] -- Distribute and zip 

現在の実装では、そのの1までzipWithを適用します引き数はリスト以外の値で、それが他のリストに分散されます。 等しい入れ子の深さに達するまで、1つの引数（より少ないリストレイヤーを持つもの）を他のものよりも優先して配布し、zipWithを使用してリスト以外の値に減らすことをお勧めします。

私の質問は次のとおりです。第2の種類の動作を達成できますか？ 私は、現在のソリューションと同様に、Haskellに演算子のタイプと各引数を明示的に伝える必要があるソリューションに満足しています。 リストを入力として扱うオペレータにはdistrを呼び出さないので、そのケースを処理する必要はありません。 しかし、タイプヒントとなるdistrに余分な引数を与えたくない場合や、さまざまなユースケースに応じて異なるバージョンのdistrをいくつか追加したいとします。 私の問題はこの方法で解決できると知っていますが、私はそれが必要でない解決策を好むでしょう。

Answer 1

（As a gist in Literate Haskell）

{-# LANGUAGE DataKinds, FlexibleContexts, FlexibleInstances, 
    TypeFamilies, MultiParamTypeClasses, UndecidableInstances, 
    RankNTypes, ScopedTypeVariables, FunctionalDependencies, TypeOperators #-} 

module Zip where 

import Data.Proxy 
import GHC.TypeLits 

てみましょう最初の2つのネストされたリストは、同じ深さを持っていることを前提としています。例えば、深さ2：

zipDeep0 ((+) :: Int -> Int -> Int) [[1,2],[3,4,5]] [[10,20],[30,40]] :: [[Int]] 
[[11,22],[33,44]] 

実装：

zipDeep0 
    :: forall n a b c x y z 
    . (ZipDeep0 n a b c x y z, n ~ Levels a x, n ~ Levels b y, n ~ Levels c z) 
    => (a -> b -> c) -> (x -> y -> z) 
zipDeep0 = zipDeep0_ (Proxy :: Proxy n) 

Levels a xは、ネストされたリスト内の型Xの深さを計算します。 クローズドタイプファミリでは、非線形タイプレベルパターンマッチング （aが句で2回発生）を実行できます。

type family Levels a x :: Nat where 
    Levels a a = 0 
    Levels a [x] = 1 + Levels a x 

我々は、 この方法では、6つの他の一般的なタイプのパラメータにのみ頼るよりもすっきりですジッパーを実装ZipDeep0インスタンスを選択するために、その深さを使用し、 それは型推論と一部重複インスタンスの問題を回避してリストは空です（したがって、 実際のタイプをそれ自体から推論することはできません）。a、b、cも リストタイプです。

class ZipDeep0 (n :: Nat) a b c x y z where 
    zipDeep0_ :: proxy n -> (a -> b -> c) -> x -> y -> z 

-- Moving the equality constraints into the context helps type inference. 
instance {-# OVERLAPPING #-} (a ~ x, b ~ y, c ~ z) => ZipDeep0 0 a b c x y z where 
    zipDeep0_ _ = id 

instance (ZipDeep0 (n - 1) a b c x y z, xs ~ [x], ys ~ [y], zs ~ [z]) 
    => ZipDeep0 n a b c xs ys zs where 
    zipDeep0_ _ f = zipWith (zipDeep0_ (Proxy :: Proxy (n - 1)) f) 

---

二つのリストは、同じ深さでない場合は、のは、第一、第二1 が深いので、我々はそれを介して配布する必要がありますと仮定しましょう。我々はいくつかの型推論を失い始める は、我々はこの機能 を適用することができ、少なくともLevels a x（および のでaとx）のいずれかLevels b yまたはLevels c z前に知っておく必要があります。

例：

zipDeep1 (+) [10,20 :: Int] [[1,2],[3,4]] :: [[Int]] 
[[11,22],[13,24]] 

実装：

zipDeep1 
:: forall n m a b c x y z 
. (n ~ Levels a x, m ~ Levels b y, m ~ Levels c z, ZipDeep1 (m - n) a b c x y z) 
=> (a -> b -> c) -> x -> y -> z 
zipDeep1 = zipDeep1_ (Proxy :: Proxy (m - n)) 

我々は戻っzipDeep0に落ちる前に通過 "を配布する" 必要がありますどのように多くの層を教えてくれる(m - n)レベルの差。どちらのリストが深く ものであってもよいとき

class ZipDeep1 (n :: Nat) a b c x y z where 
    zipDeep1_ :: proxy n -> (a -> b -> c) -> x -> y -> z 

instance {-# OVERLAPPING #-} ZipDeep0 (Levels a x) a b c x y z => ZipDeep1 0 a b c x y z where 
    zipDeep1_ _ = zipDeep0_ (Proxy :: Proxy (Levels a x)) 

instance (ZipDeep1 (n - 1) a b c x y z, ys ~ [y], zs ~ [z]) => ZipDeep1 n a b c x ys zs where 
    zipDeep1_ proxy f xs = fmap (zipDeep1_ (Proxy :: Proxy (n - 1)) f xs) 

---

最後に、我々は、タイプレベルの比較を行うことができます。私たちはすべての型推論を失います。

例：

zipDeep ((+) :: Int -> Int -> Int) [[1,2 :: Int],[3,4]] [10 :: Int,20] :: [[Int]] 
[[11,22],[13,24]] 

いくつかの型推論ではなくTypeApplicationsと の予想される深さを各リストを指定することによって回収されます。

zipDeep @2 @1 ((+) :: Int -> Int -> Int) [[1,2],[3,4]] [10,20] 
[[11,22],[13,24]] 

実装：

zipDeep 
    :: forall n m a b c x y z 
    . (ZipDeep2 (CmpNat n m) n m a b c x y z, n ~ Levels a x, m ~ Levels b y) 
    => (a -> b -> c) -> x -> y -> z 
zipDeep = zipDeep2_ (Proxy :: Proxy '(CmpNat n m, n, m)) 

class ZipDeep2 (cmp :: Ordering) (n :: Nat) (m :: Nat) a b c x y z where 
    zipDeep2_ :: proxy '(cmp, n, m) -> (a -> b -> c) -> x -> y -> z 

instance {-# OVERLAPPING #-} (n ~ Levels a x, m ~ Levels b y, m ~ Levels c z, ZipDeep1 (m - n) a b c x y z) 
    => ZipDeep2 'LT n m a b c x y z where 
    zipDeep2_ _ = zipDeep1 

instance (n ~ Levels a x, m ~ Levels b y, n ~ Levels c z, ZipDeep1 (n - m) b a c y x z) 
    => ZipDeep2 cmp n m a b c x y z where 
    zipDeep2_ _ = flip . zipDeep1 . flip