Đệ quy sử dụng danh sách - Haskell

Question

Tôi đang cố gắng viết một hàm đệ quy sẽ lấy danh sách chứa danh sách các số nguyên làm đầu vào và trả về một bộ kiểu ([Int], Int). ([Int], Int)

này là dành cho một "trò chơi hội đồng quản trị", nơi bạn được cung cấp với một bảng:

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

Đây sẽ là một bảng với 4 hàng và 5 cột. Những con số bên trong danh sách là "giá trị tiền xu". Mục tiêu của trò chơi hội đồng quản trị này sẽ là đi từ đầu danh sách xuống dưới cùng để thu thập tiền xu. Bạn có thể bắt đầu ở bất kỳ vị trí nào từ hàng trên cùng và để di chuyển xuống, bạn có thể đi thẳng xuống hoặc theo đường chéo sang trái hoặc sang phải. Bạn sẽ muốn con đường đó sẽ cung cấp cho bạn các giá trị tổng số tiền lớn nhất.

Tôi đã tạo hàm đầu tiên trong đó bạn nhập danh sách đường dẫn [([Int], Int)] và nó trả về đường dẫn ([Int], Int) với giá trị đồng xu tối đa.

Bây giờ tôi cần tạo một hàm để tạo danh sách đường dẫn mà tôi sẽ nhập vào hàm đầu tiên.

Tôi biết rằng tôi sẽ phải sử dụng đệ quy. Tôi sẽ nhập bảng (giống như trên) và cột bắt đầu. Tôi sẽ phải lấy số cột và sau đó tạo danh sách tất cả các đường dẫn có thể. Nếu tôi bắt đầu với số cột, các bước có thể tiếp theo của tôi là các vị trí (trong hàng tiếp theo) - cùng số cột, cột num -1 và cột num +1. Tôi sẽ cần phải gọi đệ quy này cho đến khi tôi đạt đến đáy.

Làm cách nào để có thể lưu trữ các bước đường dẫn này khi tôi đi và sau đó lưu trữ danh sách cuối cùng - tất cả các đường dẫn có thể?

([Int], Int) - [Int] là vị trí trong danh sách/số cột hoặc các hàng và Int là giá trị tiền xu.

Tôi mới dùng haskell và trong khi tôi hiểu những gì tôi phải làm, thật khó để viết mã.

Answer 1

Bạn không "lưu trữ" các giá trị trung gian trong một số biến trong mã chức năng thành ngữ. Thay vào đó, bạn giữ chúng như là một tham số tích lũy mà bạn vượt qua bằng cách sử dụng một hàm như foldr.

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

Answer 2

Tôi đoán Tôi bây giờ trong một vị trí để (dễ dàng) thích nghi với câu trả lời của tôi cho another question đến thế này. Tôi liệt kê các kết hợp chỉ mục được phép và ánh xạ bảng cho chúng. (Pat của comment đã giúp tôi cải thiện index_combinations)

* Main>: tải "new1.hs"
[1 trong tổng số 1] Biên soạn chính (new1.hs, giải thích)
Ok, mô-đun nạp: Main.
* Main> Kết quả
([8,7,4,9], 28)
* Main> đường
[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

Nếu bạn muốn sử dụng gói của tôi grid(userguide) đây là ví dụ để bạn bắt đầu. (Và nếu bạn không muốn sử dụng nó, bạn có thể thấy một số mã nguồn hữu ích.)

Tạo lưới có 4 hàng và 5 cột.

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

Chúng tôi muốn có thể ánh xạ "giá trị tiền xu" vào vị trí lưới, vì vậy chúng tôi sẽ tạo 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)] 

Chúng tôi có thể tìm ra những người hàng xóm của bất kỳ tế bào trong lưới, nhưng đối với ứng dụng của bạn, chúng tôi chạy vào một chút của một vấn đề: tôi loại RectSquareGrid không cho phép di chuyển theo đường chéo.

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

Bây giờ, tôi muốn được hạnh phúc để tạo ra một loại mới của Grid có thể đáp ứng nhu cầu của bạn . Ngoài ra, bạn có thể viết chức năng riêng của bạn trong đó sẽ bao gồm các nước láng giềng chéo:

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

Nhưng bạn chỉ quan tâm trong việc cho phép di chuyển lùi xuống, hoặc là thẳng xuống hoặc đường chéo, vì vậy đây là một chức năng hữu ích hơn:

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

Vì vậy, bây giờ chúng ta có thể viết một hàm cung cấp cho bạn tất cả các đường dẫn có thể có từ một chỉ mục nhất định đến hàng dưới cùng của lưới.

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 

Ví dụ:

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

Lưu ý rằng kể từ khi GridMap s cũng Grid s, chúng ta có thể gọi tất cả các chức năng nêu trên m hoặc g.

λ> allPathsFrom (0,1) m 

Hãy cho tôi biết (amy tại nualeargais chấm ie) nếu bạn muốn tôi để thêm một mạng lưới cho phép di chuyển theo đường chéo để gói grid tôi.