Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursion using lists - Haskell

I am trying to write a recursive function that will take a list containing a list of integers as an input and return a tuple of type ([Int],Int). ([Int],Int)

This is for a "board game" where you are supplied with a board:

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

This would be a board with 4 rows and 5 columns. The numbers inside the list are "coin values". The objective of this board game would be to go from the top of the list to the bottom collecting the coins. You are able to start in any position from the top row and to move down, you can go straight down, or diagonally to left or right. You would want the path that will give you the largest total coin values.

I've created a first function where you input a list of paths [([Int],Int)] and it returns the path ([Int],Int) with maximum coin value.

Now I need to create a function to actually generate the list of paths that I will input into the first function.

I know that I will have to use recursion. I will input the board (like one above) and a starting column. I will have to take the column number and then create a list of all possible paths. If I start with a column number, my next possible steps are positions (in the next row)- same column number, column num -1 and column num +1. I would need to recursively call this until I reach the bottom.

How would I be able to store these path steps as I go and then store the final - list of all possible paths?

([Int],Int) - [Int] is the position in list / column numbers or the rows and the Int is the coin value.

I'm new to haskell and while I understand what I have to do, it's really difficult to write the code.

like image 934
user2035972 Avatar asked Nov 13 '22 12:11

user2035972


1 Answers

You don't "store" intermediate values in some variable in idiomatic functional code. Rather, you keep them as an accumulating parameter which you pass along using a function such as foldr.

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

like image 137
sclv Avatar answered Dec 01 '22 09:12

sclv