递归使用列表 - Haskell

Question

我想写一个递归函数，将包含整数列表作为输入并返回类型（[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]，智力）具有最大硬币值的第一功能。

现在我需要创建一个函数来实际生成的路径列表中，我将输入到第一功能。我知道我将不得不使用递归。 我会输入板子（如上图所示）和起始栏。 我将不得不采取列号，然后创建一个所有可能的路径列表。 如果我从一个列号开始，我的下一个可能的步骤是位置（在下一行） - 相同的列号，列号-1和列号+1。我需要递归调用这个，直到达到底部。

我怎么能为我去存储这些路径步骤，然后存储最终 - 所有可能的路径列表？

（[INT]，智力） - [INT]为列表/列号或行的位置，并且INT是硬币值。

我是新来的Haskell，虽然我明白我必须做的，真的很难写的代码。

Answer 1

您不会在某些变量中将惯用功能代码中的中间值“存储”。相反，你把它们作为一个累积参数，你使用一个函数比如foldr来传递。

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

Answer 2

我想我现在是在一个位置（容易）适应我的回答对another question这一个。我列出了允许的索引组合并将它们映射到它们。 （PAT的comment帮我提高index_combinations）

*主要>：负荷 “new1.hs”
[1 1]编译主（new1.hs，解释）加载
确定，模块：主。
*主要>结果
（[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)] 

我们希望能够为“硬币值”映射到网格位置，所以我们 创建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)] 

，我很乐意创造一种新型的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 

例如：

λ> 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 s为也Grid S，我们可以调用所有上述功能上m或g。

λ> allPathsFrom (0,1) m 

让我知道（在艾米点nualeargais IE），如果你想我补充 网格允许对角线移动到我的grid包。