递归使用列表-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）。

现在我需要创建一个函数来实际生成我将输入到第一个函数中的路径列表。

我知道我将不得不使用递归。我将输入板（像上面的一个）和一个开始列。我必须取列号，然后创建所有可能路径的列表。如果我从列号开始，我接下来可能的步骤是位置（在下一行中）-相同的列号，列num-1和列num 1。我需要递归地调用它，直到我到达底部。

我如何能够存储这些路径步骤，然后存储所有可能的路径的最终列表？

（[Int]，Int）-[Int]是列表/列编号或行中的位置，Int是硬币价值。

我是haskell的新手，虽然我知道我必须做什么，但写代码真的很难。

Answer 1

如果您对使用我的软件包网格（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)]

我们希望能够将“硬币值”映射到网格位置，所以我们将创建一个GridMap。

λ> :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)]

现在，我很乐意创建一种新型的网格，满足您的需求。或者，您可以编写自己的函数，其中包括对角邻域：

λ> 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

例如：

λ> 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)]]

请注意，由于GridMap也是Grid，我们可以在m或g上调用上述所有函数。

λ> allPathsFrom (0,1) m

如果你想让我在我的网格包中添加一个允许对角线移动的网格，请告诉我（nualeargais dot ie的艾米）。

Answer 2

我想我现在可以（很容易地）把我对另一个问题的回答改编成这个问题。我列出了允许的索引组合，并将板映射到它们。（pat的评论帮助我提高了index_combinations）

*主要的

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

在惯用的函数代码中，您不会在某些变量中“存储”中间值。而是将它们作为一个累积参数，使用foldr之类的函数传递。

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