5
\$\begingroup\$

I want to understand Haskell better by trying to stretch possibilities of Functor, Applicative, and Monad as much as possible and study how they behave. So in Learn You a Haskell there's an exercise to generate all possible moves for a knight from a given position on chessboard:

moveKnight :: KnightPos -> [KnightPos]  
moveKnight (c,r) = filter onBoard  
    [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)  
    ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)  
    ]  
    where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]

Now I thought to myself, wait a second, I can actually generate that list [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1),(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)] instead of hardcoding it. So this is how I did it with list comprehensions:

invert x
  | x == 1 = 2
  | x == 2 = 1
  | otherwise = 0

moves = [(c `f` a, r `g` (invert a)) |
         c <- [6],
         r <- [2],
         f <- [(+), (-)],
         g <- [(+), (-)],
         a <- [1, 2]]

-- generates: [(7,4),(8,3),(7,0),(8,1),(5,4),(4,3),(5,0),(4,1)]

So the above works correctly, but the code looks ugly. Because every list comprehension is equivalent to a lift, the above code could be rewritten with liftA5:

liftA5 :: Applicative g => (a -> b -> c -> d -> e -> f) -> g a -> g b -> g c -> g d -> g e -> g f
liftA5 f a b c d e = f <$> a <*> b <*> c <*> d <*> e

liftA5 (\c r f g a -> (c `f` a, r `g` (invert a))) [6] [2] [(+), (-)] [(+), (-)] [1,2]

My questions are:

  • Are there any way to generate the above list in a more elegant way?
  • How to generalize it to arbitrary possible permutations? (So that my code could parametrized and not fixed to just numbers 1 and 2, or just + and -, etc)
  • What intuitions, insights and lessons can I get from this exercise?

I know that this is a massively contrived situation, but they serve me as an exercise to understand the language better.

\$\endgroup\$
1
\$\begingroup\$

Using pattern matching you can write:

invert 1 = 2
invert 2 = 1
invert n = 0 -- Error would be better in my opinion

You can inline 6 and 2 instead of taking them from a single item list.

\$\endgroup\$
1
\$\begingroup\$

I don't know about "more elegant", but there is this:

moveKnight start =
  filter onBoard $
  f (f ((,) <$> [(+),(-)] <*> [(+),(-)]) <*> [start]) <*> [(1,2), (2,1)]
  where
    onBoard = (`elem` ((,) <$> [1..8] <*> [1..8]))
    f = map $ uncurry (***)

That needs a better name for f of course. The [(1,2), (2,1)] can be generated by (filter (uncurry (/=)) $ (,) <$> [1,2] <*> [1,2]), but that seems overkill.

\$\endgroup\$
  • \$\begingroup\$ I would argue that such use of Applicatives & Arrows is far from elegant, as elegance rests on simplicity & clarity. \$\endgroup\$ – recursion.ninja Jul 23 '15 at 15:40
  • \$\begingroup\$ Perhaps; one could also argue though that the original solution brought in unnecessary monad machinery, and it's more elegant to avoid the implicit imperative ordering monadic style enforces. It's probably a losing argument, but I think it's worth considering. \$\endgroup\$ – Daniel Martin Jul 23 '15 at 16:35
  • \$\begingroup\$ I agree that is it "more elegant", just not objectively elegant. I remember recently toying with an Applicative solution for knight's move generation on and off for about a week before I settled on a different solution I thought was more elegant. I'll see if I can find it and post it as an answer. \$\endgroup\$ – recursion.ninja Jul 23 '15 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.