1

I am trying to implement famous Verbal arithmetics problem (SEND + MORE = MONEY) in Haskell. For those who don't know about verbal arithmetics- https://en.wikipedia.org/wiki/Verbal_arithmetic.

This is my sample program, however for some reason it does not work, it returns an empty list. Could anyone point out the flaw in the code and give some suggestions? I am stuck, thank you! 

expand' a b c d e = e + d*10 + c*100 + b*1000 + a*10000
expand'' a b c d = d + c*10 + b*100 + a*1000

digits = [0,1..9]  -- all the digits

answer = head [ list | list@[s,e,n,d,m,o,r,y] <- perm digits,
   expand'' s e n d +  expand'' m o r e == expand' m o n e y]

--unique permutation
perm :: [t] -> [[t]]
perm [] = [[]]
perm (x:xs) = [(y:zs) | (y,ys) <- del (x:xs), zs <- perm ys]

--deleting duplicates
del :: [t] -> [(t,[t])]
del [] = []
del (x:xs) = ((x,xs) : [ (y,(x:ys)) | (y,ys) <- del xs ])


main :: IO()
main = do
   print  answer

The solution was inspired by: http://www.dcs.gla.ac.uk/mail-www/haskell/msg01929.html

Vladyslav Babych
  • 123
  • 9
  • 1
    `perm digits` returns only lists of length 10, but `list@[s,e,n,d,m,o,r,y] <- perm digits` requires that `list` be of length 8. This causes a pattern match failure. A quick fix could be to use `list@[s,e,n,d,m,o,r,y,_,_] <- perm digits` instead. – rampion Jan 30 '16 at 22:17
  • @rampion Thank you very much! – Vladyslav Babych Jan 30 '16 at 22:23
  • @rampion I can see that output produces some extra numbers, such as 3 and 4, which should not be included in the result, because the solution is: 9567+1085=10652 ([9,5,6,7,1,0,8,2]) Do you have any suggestions how this can be fixed? Thanks! – Vladyslav Babych Jan 30 '16 at 22:31
  • cf also https://stackoverflow.com/questions/14873315/dynamic-list-comprehension-in-haskell/ – Will Ness Jan 30 '16 at 23:47

1 Answers1

1

The main problem is that perm digits returns only lists of length 10, but list@[s,e,n,d,m,o,r,y] <- perm digits requires that list be of length 8. This causes a pattern match failure.

Pattern match failures are silent in list comprehensions - they're useful for filtering input (specifyingy you only care about matches), which can cause issues at times.

A quick fix could be to use [ [s,e,n,d,m,o,r,y] | list@[s,e,n,d,m,o,r,y,_,_] <- perm digits, ... ] instead.

Some other suggestions:

  • You can replace expand' and expand'' by a single expand. It looks like you're using this as a learning expereince, so I'll just give you a hint: expand [s,e,n,d] + expand [m,o,r,e] == expand [m,o,n,e,y]
  • del is somewhat deceptively named. It doesn't delete anything, it just creates all the possible views (x_j, [x_0,...,x_{j-1},x_{j+1},...x_{n-1}]) of an n-length list [x_0,...,x_{n-1}]
  • You could write a version of perm that took another parameter specifying the number of elements in the permutation, so perm k [1..n] returned all the permutations of k distinct elements drawn from [1..n]. If you wanted to generate ALL the solutions, this might be helpful.
rampion
  • 87,131
  • 49
  • 199
  • 315