My solution to problem #5 of five problems that every “real programmer” should be able to do except the guy who posted them screwed up #4 himself.

01_hundreds.hs

-- Problem statement:
-- Write a program that outputs all possibilities to put + or - or nothing between the
-- numbers 1, 2, ..., 9 (in this order) such that the result is always 100.
-- For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

data Item = Plus | Minus | Num Int deriving (Show)

hundreds = filter ((100 ==) . eval) $ map combineAdjacent $ combos [1..9]

-- Generate all combos of digits 1-9 with +, -, or nothing in between.
combos :: [Int] -> [[Item]]
combos [n]    = [ [Num n] ]
combos (n:ns) = [ (Num n : x) ++ rest | x <- [[Plus], [Minus], []], rest <- combos ns ]

-- Combine adjacent digits into a single number.
combineAdjacent :: [Item] -> [Item]
combineAdjacent (Num n : Num m : rest) = combineAdjacent (Num (n * 10 + m) : rest)
combineAdjacent (Num n : op : rest)    = Num n : op : combineAdjacent rest
combineAdjacent x                      = x

-- Now eval the resulting thing as a left-associative expression.
eval :: [Item] -> Int
eval (Num n : Plus : Num m : rest)  = eval (Num (n + m) : rest)
eval (Num n : Minus : Num m : rest) = eval (Num (n - m) : rest)
eval [ Num n ]                      = n

display xs = foldl (++) "" (map d xs) where
    d Plus    = " + "
    d Minus   = " - "
    d (Num n) = show n

main = mapM_ (putStrLn . display) hundreds

02_another.hs

-- For further grins: here's a Haskell version of something like his solution.

hitTarget :: Int -> [Int] -> [[Int]]
hitTarget 0 [] = [[]]
hitTarget _ [] = []
hitTarget target (d:ds) = plus ++ minus ++ combined where
    plus     = [ d:x | x <- hitTarget (target - d) ds ]
    minus    = [ -d:x | x <- hitTarget (target + d) ds ]
    combined = if null ds then [] else hitTarget target ((d * 10 + head ds) : tail ds)

display :: [Int] -> String
display (n:ns) = foldl (++) (show n) (map withSign ns) where
    withSign n | n > 0 = " + " ++ show n
    withSign n | n < 0 = " - " ++ show (abs n)

hundreds = filter ((>0) . head) $ hitTarget 100 [1..9]

main = mapM_ (putStrLn . display) hundreds

I think you can simplify the generation of the list of items:

items  = do
    n  <- [1..9]
    xs <- if n == 9 then [] else [[Plus], [Minus], []]
    Num n:xs

Also you can simplify display a little bit:

foldl (++) "" (map d xs) = concatMap d xs

Also, you can simplify hundreds a little bit by fusing the filter and map (stream fusion!)

filter ((100 ==) . eval . combineAdjacent) (combos [1..9])

I like the concatMap (I thought there was something like that but I couldn't find it) and the fusion. But that do expression doesn't produce the right thing at all.

Gabriel, here's what I came up with which is not at all like your do expression but was inspired by trying to figure out what you were getting at. This replaces combos [1..9].

expressions :: [[Item]]
expressions = foldl cross [[]] (map withOp [1..9]) where
    withOp n = [ Num n : x | x <- if n == 9 then [[]] else [[Plus],[Minus],[]] ]
    cross xs ys = [ x ++ y | x <- xs, y <- ys ]

Actually, I think my filter fusion is totally incorrect, so ignore that one.

Also, I think I managed to fix the items one:

import Control.Monad (forM)

data Item = Num Int | Plus | Minus deriving (Show)

items :: [[Item]]
items = do
    -- Example `groups` value: [[Num 1, Plus], [Num 2], ... [Num 8, Minus]]
    groups <- forM [1..8] (\n -> do
        xs <- [[Plus], [Minus], []]
        return (Num n:xs) )
    return (concat groups ++ [Num 9])

forM is basically "foreach" in Haskell, except it works with arbitrary monads and collects the results in a list. Here I'm just saying "generate 8 groups", except that the result of each group is allowed to vary using the list monad. Then concatenate those groups and tack on Num 9 at the end.