入れ子リストHaskell反復

Question

Haskellで入れ子リスト操作を実装する必要があります。

f :: [[String]] -> [[String]] 

私の入力は、私が任意にそのリストを生成した2次元配列

[ [ ”A” , ”A” , ”A” ] 
, [ ”B” , ”B” , ”A” ] 
, [ ”A” , ”A” , ”B” ] ] 

です。

A A A 
B B A 
A A B 

私の実装では、次のことを行う必要があります。

• 位置を有し、それは2を有するか、または2つ以上の「B」隣人位置Bを有し、それは2又は2つ以上の「Bがある場合、それはB.
• に変わります場合"隣人のように、それはそのままです。
• 位置はBを持っており、それが2未満「B」隣人を持っている場合、それはそう第一工程の後に私のテーブルは次のようになりますA.

に変わります。

B B A 
A B B 
B B A 

私はCまたはC++を使用するつもりだった場合、私のアルゴリズムはこれをたいと思います：

1. 私の入力のコピーを作成します。

2. 2forループ内の両方のリストをトラバースし、場所を変更する場合はif文をチェックし、変更を行う場合は最初のリストを変更することで最初のリストをトラバースするようにします他の "A"と "B" 'に影響しません。

3. 第2リストを返します。

問題は、ハスケルでは、私は反復を使用できません。どうすればこの問題を解決できますか？

Answer 1

私がコメントで述べたように、再帰はHaskellのループプリミティブです。しかし、Haskellは再帰を直接使用するのではなく、よりユーザーフレンドリな抽象化を構築するための多くの力を私たちに提供します。 @Lazersmokeが述べたように、Comonadはコレクションの他の値（値の隣人など）に基づいてコレクションの個々の値を更新するときのよい抽象です。

Comonadクラスの例はウェブ上にはたくさんありますが、悲しいかなかMonadによって覆われています。だから、ここでも私のスコアに少しでもしようとしています。

これは長いポストになるので、私は結果から始めましょう。これはGHCiからのものです：

λ display example 
[[A,A,A],[B,B,A],[A,A,B]] 
λ display (transition example) 
[[B,B,A],[A,B,B],[B,B,A]] 

[OK]を今すぐビジネスに着きましょう。最初の数行政の事：

module Main where 
import Control.Comonad -- from the comonad package 

私は慎重に各部分を説明しようとするつもりだけど、大きな画像が明らかになる前に、それはしばらく時間がかかることがあります。まず、ジッパーと呼ばれる興味深いデータ構造を作成し、Functorのインスタンスを実装します。

data U x = U [x] x [x] deriving Functor 

instance Functor U where 
    fmap f (U as x bs) = U (fmap f as) (f x) (fmap f bs) 

このデータ構造はあまり特別ではないようです。それは我々がそれを冷やすようにUを使用する方法です。 Haskellは怠惰なので、Uコンストラクタで無限リストを使うことができます。たとえば、i1 = U [-1,-2..] 0 [1,2..]はすべての整数を表します。しかし、それだけではありません。別の情報があります。中心点は0です。すべての整数をi2' = U [0,-1..] 1 [2,3..]とすることもできます。これらの値はほとんど同じです。彼らはちょうど1つだけシフトされます。実際には、一方を他方に変換する関数を作成することができます。

rightU (U a b (c:cs)) = U (b:a) c cs 
leftU (U (a:as) b c) = U as a (b:c) 

あなたが見ることができるように、私たちはただの要素を再配置することにより、左または右にスライドUをすることができます。 UのインスタンスをShowにして、rightUとleftUが機能することを確認します。私たちは明らかに無限のリストを印刷することはできないので、それぞれの面から3つの要素を取ります。

instance Show x => Show (U x) where 
    show (U as x bs) = (show . reverse . take 3) as ++ (show x) ++ (show . take 3) bs 

λ i1 
[-3,-2,-1]0[1,2,3] 
λ leftU i2 
[-3,-2,-1]0[1,2,3] 
λ i2 
[-2,-1,0]1[2,3,4] 
λ rightU i1 
[-2,-1,0]1[2,3,4] 

究極の目標を確認しましょう。私たちは、すべての隣人に基づいて各値を更新できるデータ構造を作りたいと思っています。私たちのUデータ構造でそれを行う方法を見てみましょう。各数値をその近傍の和で置き換えたいとします。

sumOfNeighbors :: U Int -> Int 
sumOfNeighbors (U (a:_) _ (b:_)) = a + b 

そして、ちょうどそれが動作することを確認する：まずは、Uの現在位置の近傍を計算する関数を書いてみましょう

λ sumOfNeighbors i1 
0 
λ sumOfNeighbors i2 
2 

は残念ながら、これは私たちだけに単一の結果を提供します。この機能をあらゆる可能な位置に適用したいと考えています。よくUにはFunctorのインスタンスがあるので、fmapの関数を使用できます。私たちの関数がInt -> Intのような型を持っていればそれはうまくいくでしょうが、それは実際にはU Int -> Intです。しかし、もしU IntをU (U Int)にすることができたら？その後、fmap sumOfNeighborsは、私たちが望むものを正確に行うでしょう！

いくつかの初歩レベルのデータ構造を用意してください。私たちは、U Intを取ると、次のようになりますU (U Int)を作成しようとしている：

-- not real Haskell. just for illustration 
U [leftU u, (leftU . leftU) u, (leftU . leftU . leftU) u..] u [rightU u, (rightU . rightU) u, (rightU . rightU . rightU) u..] 

この新しいU (U a)のこのセンターは、元U aです。左にスライドすると元のU aが左にスライドし、同様に右にスライドします。言い換えれば、新しいU (U a)はここで、我々はそれを行う方法です元U aのすべての左と右のスライドが含まれています

duplicate :: U a -> U (U a) 
duplicate u = U lefts u rights 
    where lefts = tail $ iterate leftU u 
     rights = tail $ iterate rightU u 

私たちは、私たちが望む機能の書き込みにduplicateを使用することができます。

extend :: (U a -> b) -> U a -> U b 
extend f = fmap f . duplicate 

をそれを試してみましょう。

λ extend sumOfNeighbors i1 
[-6,-4,-2]0[2,4,6] 

このように見えます。これらの関数名、duplicateとextendは、少なくとも私が選んだものではありませんでした。これらの関数はComonad型クラスの一部です。 Uのデータ型用に実装しています。

class Functor w => Comonad w where 
    extract :: w a -> a 
    duplicate :: w a -> w (w a) 
    extend :: (w a -> b) -> w a -> w b 

唯一欠けているUための簡単ですextractです：

extract (U _ x _) = x 

それは、このクラスがまだあるか便利おそらく明白ではありません。 2次元の場合をどのように扱うかを見てみましょう。私たちはジッパーのジッパーで2次元を行うことができます。すなわち、U (U a)は左右に動かすと内側のジッパーが移動し、上下に動くと外側のジッパーが移動します。

newtype V a = V { getV :: U (U a) } 

instance Functor V where 
    fmap f = V . (fmap . fmap) f . getV 

-- shift the 'outer' zipper 
up :: V a -> V a 
up = V . leftU . getV 

down :: V a -> V a 
down = V . rightU . getV 

-- shift the 'inner' zippers 
left :: V a -> V a 
left = V . fmap leftU .getV 

right :: V a -> V a 
right = V . fmap rightU . getV 

はここComonadがVのために次のようになります。

instance Comonad V where 
    extract = extract . extract . getV 
    duplicate = fmap V . V . dup . dup . getV 
    where dup u = U (lefts u) r (right u) 
      lefts u = tail $ iterate (fmap leftU) u 
      rights u = tail $ iterate (fmap rightU) u 

extract機能は非常に簡単です。それはちょうど現在の値をつかむためにジッパーの2つの層を掘るだけです。一方、duplicateは、ある種のモンスターです。新しいタイプVを無視すると、タイプはduplicate :: U (U a) -> U (U (U (U a)))になります。 dupヘルパー機能の目的は、Uレイヤーを追加することです。それは2回呼び出されます。次にVにそれを書き込んでV (U (U a))にします。次にfmap VはU (U a)の結果をV (V a)にするために内部をラップします。

ところで、extendがどこにあるのか疑問に思っているのであれば、実際には書き込む必要はありません。上記の定義はデフォルトです。

これはたくさんの作業でしたが、今すぐ元の問題に取り組むことができます。これをチェックしてください。私はあなたのAとB値を含むデータ構造を作るつもり、とも私たちは気にしない値、Cだ：

data Token = A | B | C deriving (Eq,Show) 

そして、ここでは簡単にVを構築し、表示を行うためにいくつかのものです。

example = toV C ((A,A,A) 
       ,(B,B,A) 
       ,(A,A,B)) 

とルールがによって実装されています：

：最後に、我々は extendを使用して、すべての値に ruleを適用することができます

-- move into each neighboring position and get the value in that position 
neighbors :: V a -> [a] 
neighbors v = fmap (extract . ($ v)) positions 
    where positions = [ up . left 
        , up 
        , up . right 
        , left 
        , right 
        , down . left 
        , down 
        , down . right ] 

numberOfBs :: V Token -> Int 
numberOfBs = length . filter (==B) . neighbors 

rule :: V Token -> Token 
rule v = case extract v of 
    C -> C -- C's remain C's forever 
    _ -> if numberOfBs v >= 2 then B else A 

ここ

-- a list of U's containing nothing but x's 
filled x = repeat $ U (repeat x) x (repeat x) 

type Triple a = (a,a,a) 

-- create a U with the middle values a, b, and c, and all the other values the defaulted to d 
toU :: a -> Triple a -> U a 
toU d (a,b,c) = U (a : repeat d) b (c : repeat d) 

-- create a V centered on the 9 given values and default all other values to d 
toV :: a -> Triple (Triple a) -> V a 
toV d (as, bs, cs) = V (U x y z) 
    where x = (toU d as) : filled d 
     y = toU d bs 
     z = (toU d cs) : filled d 

display :: Show a => V a -> [[a]] 
display v = fmap g [ [up . left, up, up . right] 
        , [left, id, right] 
        , [down . left, down , down . right] ] 
    where g = fmap (extract . ($ v)) 

は一例は次のようになります。

transition = extend rule 

λ display (transition example) 
[[B,B,A],[A,B,B],[B,B,A]] 

このルールはちょっと退屈です。すべてがすぐにBになる。

λ take 10 $ fmap display (iterate transition example) 
[[[A,A,A],[B,B,A],[A,A,B]],[[B,B,A],[A,B,B],[B,B,A]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]]] 

異なるルールを作成するのは簡単です。

rule2 :: V Token -> Token 
rule2 v = case extract v of 
    C -> C 
    A -> if numberOfBs v >= 2 then B else A 
    B -> if numberOfBs v >= 4 then A else B 

λ take 10 $ fmap display (iterate (extend rule2) example) 
[[[A,A,A],[B,B,A],[A,A,B]],[[B,B,A],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]]] 

クール、右？私が言いたい最後のひとつ。エッジを処理する特別なケースは記述していないことに気がつきましたか？データ構造は無限であるので、値域Cで気にしない範囲のものを埋めて、それを無視して隣人を考える。