NO HARD CODING For this

#1

So the issue I have is one that, some suggested, just hard code. Since its for a finite set of things.
But thats lame.

It involved some self created data , types etc. So I already broke down the problem to a smaller problem
and thats the one I will pose here.

I now have a list of elements, only 1, 0, 2
[1,0,2, 0,0,0,2,2,1] for example. so [Int], let’s call it stateZero

I have supplied this board for example together with either a 1 or a 2
and a zero can turn into either 1 or 2.

so I need to collect what new lists could be created from this list if you can change any single 0

so say we are given 1, we could get from stateZero to

[1, 1, 2, 0, 0, 0, 2, 2, 1], or [1,0,2,1,0,0,2,2,1] or [1,0,2,0,1,0,2,2,1] or [1,0,2,0,0,1,2,2,1]

these possible results I need to get all into a list so a [ [Int] ]
How to do that ? Like this would be so easy in non-functional language with some looping
and indexing, setting elements.

I want to get this with a list comphrension like so

func i (x:xs) = [ [(y:ys)] | x < xs, x == 0]
where
y = i

it looks kinda fked up, but then again I don’t want this to become too complicated with functions all over the place for something so…simple right?

#2

It is also pretty simple in Haskell:

f _ [] = []
f i (0 : xs) = (i : xs) : map (0 :) (f i xs)
f i (x : xs) = map (x :) (f i xs)

I don’t think a list comprehension is useful in this case. Or perhaps only to replace the map:

f _ [] = []
f i (0 : xs) = (i : xs) : [0 : ys | ys <- f i xs]
f i (x : xs) = [x : ys | ys <- f i xs]
#3

Thanks for answering! Looks indeed like a very elegant solution…

I don’t fully understand this part: map (0: ) (f i xs)

after the 0 : why is there a closing bracket.

#4

The map function expects a function as its first argument, that function will then be mapped over the list which is given as its first argument.

In Haskell you have a special syntax for making a new function from a partially applied operator, called operator sections. If you just leave out one of the arguments then you get a partially applied function as result.

For example you have (+ 1) which is equivalent to \x -> x + 1, taking one argument and incrementing it by one.

The operator (:) normally prepends its first argument as an element to its second argument as a list. If you write (0 :) then that is equal to \x -> 0 : x, which is a function that prepends the number 0 its argument.

Altogether the expression map (0 :) (f i xs) prepends the number 0 to all lists produced by the recursive call f i xs.

#5

@jaror gave an excellent answer about operator sections. That’s just a bit of new syntax to learn.

I think some names and comments can also make @jaror’s answer a little clearer, especially for a beginner:

type Board = [Int]
type Player = Int

-- movesForPlayer takes a Player and a Board, and returns
-- a list of possible Boards after that Player's move.
movesForPlayer :: Player -> Board -> [Board]
-- An empty Board has no possible moves
movesForPlayer player [] = []
-- If the space is empty, the Player can move here or elsewhere.
movesForPlayer player (0 : spaces) =
  (player : spaces) : map (0 :) (movesForPlayer player spaces)
-- If the space is full, the Player must move elsewhere.
movesForPlayer player (space : spaces) =
  map (space :) (movesForPlayer player spaces)

A more idiomatic version might look like this:

type Board = [Maybe Player]
data Player = X | O

stateZero :: Board
stateZero =
  [ Just X,
    Nothing,
    Just O,
    Nothing,
    Nothing,
    Nothing,
    Just O,
    Just O,
    Just X
  ]

-- movesForPlayer takes a Player and a Board, and returns
-- a list of possible Boards after that Player's move.
movesForPlayer :: Player -> Board -> [Board]
-- An empty Board has no possible moves
movesForPlayer player [] = []
-- If the space is empty, the Player can move here or elsewhere.
movesForPlayer player (Nothing : spaces) =
  (player : spaces) : map (Nothing :) (movesForPlayer player spaces)
-- If the space is full, the Player must move elsewhere.
movesForPlayer player (Just space : spaces) =
  map (Just space :) (movesForPlayer player spaces)

What I’ve changed is:

  1. Defining an algebraic data type for players, so that you can’t represent impossible values like 42.
  2. Using the type Maybe Player for a space, indicating that either a player has moved there, or not.
4 Likes
#6

Just my two cents regarding your comment how easy looping is in non-functional languages compared to functional ones.

In the past I could always replace loops with folds or maps. In your example, I would first try to generate a list of indexes of the zeros. Then I would just use foldl to iterate over these indexes. In the accumulator I would have a list of lists used for accumulating the different combinations based on the index.