リストを使用した再帰 - Haskell

Question

整数のリストを含むリストを入力として受け取り、型（[Int]、Int）のタプルを返す再帰関数を作成しようとしています。 （[INT]、INT）

これは、あなたがボードに付属している "ボードゲーム" のためである：

[[5,4,3,8,6], 
    [0,2,1,0,7], 
    [0,1,9,4,3], 
    [2,3,4,0,9]] 

これは、4行5列のボードになります。リスト内の数字は「コイン値」です。 このボードゲームの目的は、リストの上部からコインを収集する下部に行くことです。一番上の行から任意の位置で開始し、下に移動することができます。まっすぐ下に移動することも、左または右に斜めに移動することもできます。あなたはあなたに最大の合計コイン値を与えるパスが必要になります。

パス[（[Int]、Int）]のリストを入力し、最大コイン値を持つパス（[Int]、Int）を返す最初の関数を作成しました。

これで、実際に最初の関数に入力するパスのリストを生成する関数を作成する必要があります。

私は再帰を使用する必要があることを知っています。 上記のようなボードと開始列を入力します。 私は列番号を取って、すべての可能なパスのリストを作成する必要があります。 私が列番号で始める場合、次のステップは次の行の位置です - 同じ列番号、列番号-1、列番号+1です。私が底に達するまで、これを再帰的に呼び出す必要があります。

私はこれらのパスステップを保存して、すべての可能なパスの最終リストを保存することができますか？

（[Int]、Int） - [Int]はリスト/列番号または行の位置で、Intはコインの値です。

私はhaskellが新しく、私は何をしなければならないか理解している間に、コードを書くのは本当に難しいです。

Answer 1

中間変数を慣用関数コードの変数に「格納」しないでください。むしろ、foldrのような関数を使って渡す累積的なパラメータとしてそれらを保持します。

http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr

Answer 2

私は（簡単に）この1へanother questionのための私の答えを適応する立場になりましたよね。私は許可されたインデックスの組み合わせを列挙し、それらにボードをマッピングしました。ロード "new1.hs"
[1 1]
[OK]を、モジュールがロードされ、メイン（new1.hs、解釈）をコンパイル：メインメイン> *

（パットのcommentは私がindex_combinationsを向上させる助けました）。
*メイン>結果
（[8,7,4,9]、28）
*メイン>パス
[3,4,3,4]

import Data.List 
import Data.Ord 
import Data.Maybe 

r = [[5,4,3,8,6], 
    [0,2,1,0,7], 
    [0,1,9,4,3], 
    [2,3,4,0,9]] 

r1 = r !! 0 
r2 = r !! 1 
r3 = r !! 2 
r4 = r !! 3 

index_combinations = 
    [[a,b,c,d] | a <- [0..4], b <- [max 0 (a-1)..min 4 (a+1)], 
    c <- [max 0 (b-1)..min 4 (b+1)], d <- [max 0 (c-1)..min 4 (c+1)]] 

mapR xs = [r1 !! (xs !! 0), r2 !! (xs !! 1), 
      r3 !! (xs !! 2), r4 !! (xs !! 3)] 

r_combinations = map mapR index_combinations 
r_combinations_summed = zip r_combinations $ map (foldr (+) 0) r_combinations 

result = maximumBy (comparing snd) r_combinations_summed 
path = index_combinations !! fromJust (elemIndex result r_combinations_summed) 

Answer 3

あなたがしている場合私のパッケージを使用することに興味があります。grid(userguide) ここをクリックして始めましょう。 （使用したくない場合は、 ソースコードの一部が役立つ場合があります。）

4行5列のグリッドを作成します。

λ> :m + Math.Geometry.Grid 
λ> let g = rectSquareGrid 4 5 
λ> indices g 
[(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3),(4,0),(4,1),(4,2),(4,3)] 

私たちは、グリッド位置に「コイン値を」マッピングすることができるようにしたいので、我々は グリッドマップを作成します。

λ> :m + Math.Geometry.GridMap 
λ> let m = lazyGridMap g [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9] 
λ> m 
lazyGridMap (rectSquareGrid 4 5) [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9] 
λ> toList m 
[((0,0),5),((0,1),4),((0,2),3),((0,3),8),((1,0),6),((1,1),0),((1,2),2),((1,3),1),((2,0),0),((2,1),7),((2,2),0),((2,3),1),((3,0),9),((3,1),4),((3,2),3),((3,3),2),((4,0),3),((4,1),4),((4,2),0),((4,3),9)] 

我々は、グリッド内の任意のセルの隣人を見つける が、あなたのアプリケーションのために、我々は問題のビットに実行することができます：私の RectSquareGrid型は対角の移動を許可していません。

λ> neighbours (1,2) m 
[(0,2),(1,3),(2,2),(1,1)] 

さて、私はあなたの のニーズを満たすでしょうGridの新しいタイプを作成させていただきます。また、あなたは斜めの隣人が含まれる独自の機能 を書くことができ：

λ> let neighbours2 (x, y) g = filter (`inGrid` g) [(x-1,y-1), (x-1,y), (x-1,y+1), (x,y-1), (x,y+1), (x+1,y-1), (x+1,y), (x+1,y+1)] 
λ> neighbours2 (1,2) m 
[(0,1),(0,2),(0,3),(1,1),(1,3),(2,1),(2,2),(2,3)] 

しかし、あなたはどちらかまっすぐまたは斜め下方に移動することが可能で唯一の興味なので、ここではより多くの便利な機能があります：

λ> let allowedMoves (x, y) g = filter (`inGrid` g) [(x+1,y-1), (x+1,y), (x+1,y+1)] 
λ> allowedMoves (1,2) m 
[(2,1),(2,2),(2,3)] 

これで、グリッドの特定のインデックスから一番下の行までのすべての可能なパスを提供する関数を書くことができます。例えば

allPathsFrom a g | fst a == fst (size g) = [[a]] 
       | otherwise    = Prelude.map (a:) xs 
    where xs = concatMap (\x -> allPathsFrom x g) ys 
     ys = allowedMoves a g 

：GridMap sはGrid Sもあるので、我々はm又はgに上記の機能のすべてを呼び出すことができること

λ> allPathsFrom (0,1) m 
[[(0,1),(1,0),(2,0),(3,0),(4,0)],[(0,1),(1,0),(2,0),(3,0),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,0)],[(0,1),(1,0),(2,0),(3,1),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,0),(4,0)],[(0,1),(1,0),(2,1),(3,0),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,0)],[(0,1),(1,0),(2,1),(3,1),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,1)],[(0,1),(1,0),(2,1),(3,2),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,0),(3,0),(4,0)],[(0,1),(1,1),(2,0),(3,0),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,0)],[(0,1),(1,1),(2,0),(3,1),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,0),(4,0)],[(0,1),(1,1),(2,1),(3,0),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,0)],[(0,1),(1,1),(2,1),(3,1),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,1)],[(0,1),(1,1),(2,1),(3,2),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,1),(4,0)],[(0,1),(1,1),(2,2),(3,1),(4,1)],[(0,1),(1,1),(2,2),(3,1),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,1)],[(0,1),(1,1),(2,2),(3,2),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,3),(4,2)],[(0,1),(1,1),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,1),(3,0),(4,0)],[(0,1),(1,2),(2,1),(3,0),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,0)],[(0,1),(1,2),(2,1),(3,1),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,1)],[(0,1),(1,2),(2,1),(3,2),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,1),(4,0)],[(0,1),(1,2),(2,2),(3,1),(4,1)],[(0,1),(1,2),(2,2),(3,1),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,1)],[(0,1),(1,2),(2,2),(3,2),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,3),(4,2)],[(0,1),(1,2),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,3),(3,2),(4,1)],[(0,1),(1,2),(2,3),(3,2),(4,2)],[(0,1),(1,2),(2,3),(3,2),(4,3)],[(0,1),(1,2),(2,3),(3,3),(4,2)],[(0,1),(1,2),(2,3),(3,3),(4,3)]] 

注意。

λ> allPathsFrom (0,1) m 

あなたは私が 私のgridパッケージに斜めの移動が可能にグリッドを追加したい場合（nualeargaisでエイミーはすなわちドット）私を知ってみましょう。