The import is needed for Gunter's version.

> import Maybe ( catMaybes )

> type Picture = [ String ]


Re: S. Thompson's book, exercises 10.16 & 10.17

Michael Scheurig said:

Due to their context, I take the intention behind these exercises to 
practice the use of (a) functions as arguments to other functions (b) 
function composition (c) partial application of functions. That is, 
it's not enough just to find _a_ solution, but there will be solutions 
that are better or worse judged by these criteria.

Ex. 10.16
The object of this exercise is to write a function that takes the 
description of a picture and generates the actual picture. 

E.g., 

makePicture 7 5 [(1, 3), (3, 2)]

should create this picture (when printed)

.......
...#...
.......
..#....
.......


> makePicture        :: Int -> Int -> [(Int, Int)] -> Picture
> makePicture width height dots
>     = map (\h -> map (drawDot h) [0..width-1]) [0..height-1]
>     where 
>     isBlack x y     = elem (x, y) dots
>     drawDot x y
>       | isBlack x y = '#'
>       | otherwise   = '.'


This function meets the spec -- but without composition or partial 
application. I'd expect there to be some way to replace lambda with 
some magical partial application of the inner map, but I haven't got 
any clue how this may look.

Ex. 10.17
This exercise asks for the inverse function of makePicture. In an 
imperative language the natural solution would be to enumerate the 
indexes and test each dot whether it's black. In Haskell this can be 
done with the !! operator -- unfortunately, this is O(n) on the lists 
used to implement pictures. It doesn't seem very FPesque either.

So here's what I've come up with

> indexedElements :: [a] -> [(Int, a)]
> indexedElements l = zip [0..(length l)-1] l

> pictureRep :: Picture -> ( Int, Int, [(Int, Int)] )
> pictureRep pic = ( width, height, dots )
>    where 
>       height = length pic
>       width 
>  	 | height > 0 = length (head pic)
>  	 | otherwise = 0
>       dots = concat 
>           (map 
>               (\(y, row) ->
>                   [ (y, x) | (x, dot) <- (indexedElements row), dot == '#' ])
>               (indexedElements pic))

Again, there must be a more idiomatic solution.


Michael

(End of Michael Scheurig's message.)


Gunter's implied version:

> gunterRep :: Picture -> ( Int, Int, [(Int, Int)] )
> gunterRep pic = ( width, height, dots )
>    where 
>       height = length pic
>       width 
>  	 | height > 0 = length (head pic)
>  	 | otherwise = 0
>       dots = catMaybes $ concat $ zipWith onRows [0..] pic
>           where onRows rNum = zipWith onDot [0..]
>                               where onDot cNum '#' = Just (rNum, cNum)
>                                     onDot _    '.' = Nothing


Here's my (Doug L.'s) take on it:

My first guess was that at least one of the partial application(s)
you might want has to do with "(== '#')".

Style note:  Note that the tuples (pairs) given as "correct" are
backwards from the normal (x,y) notation.  So it's quite confusing
for anyone to use x and y in the solution:  you should IMHO be
consistently using "row" and "column" or "r" and "c" instead.

My first cut at the problem uses list comprehensions; these
seem the most straightforward solutions to me:

    The answer is a list of rows (a list comprehension);
    a row is a list of symbols (another list comp.);
    each symbol is '#' or '.' as dotLocs tells us.


> dalMkPic :: Int -> Int -> [(Int, Int)] -> Picture
> dalMkPic width height dotLocs =
>      let  sym c r = if  elem (r, c) dotLocs  then '#' else '.'
>           row n = [ sym c n | c <- [0..width-1] ]
>      in [ row n | n <- [0..height-1] ]

The other direction (starting with a Picture) seems
equally straightforward:

> dalRep :: Picture -> ( Int, Int, [(Int, Int)] )
> dalRep pic = ( width, height, filter isSharp allPairs)
>  where height = length pic
>        width = if height > 0 then length (head pic) else 0
>        isSharp (r,c) = ((pic !! r) !! c) == '#'
>        allPairs = [ (r,c) | r <- [0..height-1], c <- [0..width-1] ]

However, these don't use any function composition nor
partial application.



My second try consciously avoided list comprehensions, since
I don't know whether Thompson has described those at that point
in his book.  For this attempt, I only did the second part.
Naming each intermediate result helped a little, but this
just ended up looking too convoluted.  It does use functions
passed to other functions, but still not much partial application
or composition.

This one goes like this:
  (withRowNr) replace the list of rows with a list of pairs
       of row-number and the row
  (mkTriples) given a row, turn each '.' or '#' into a triple
       of (row number, column number, '.' or '#' )
  (asTriples) do mkTriples on all of the rows
  (whoCares) retain only the triples that have a '#'


> dal2Rep :: Picture -> ( Int, Int, [(Int, Int)] )
> dal2Rep pic =
>    let  height = length pic
>         width = if height > 0 then length (head pic) else 0
>         withRowNr = zip [0..height-1] pic
>         mkTriples (rnr,cols) = zip3 (repeat rnr) [0..width-1] cols
>         asTriples = map mkTriples withRowNr
>         isSharp (_,_,ch) = ch == '#'
>         whoCares = filter isSharp (concat asTriples)
>         twoOfThree (r,c,_) = (r,c)
>    in
>         ( width, height, map twoOfThree whoCares )


Building up triples, filtering them, and then selecting two of the
three items to turn each relevant triple back into a pair seemed
like a bit too much work -- so I finally hit on the idea of a
function ("sharpCols", below) which would instead just return the
list of columns that contain a '#'.  This led to the following
version of the *Rep part of the problem: 

> dal3Rep :: Picture -> ( Int, Int, [(Int, Int)] )
> dal3Rep pic =
>    let  height = length pic
>         width = if height > 0 then length (head pic) else 0
>         addColNr = zip [0..width-1]
>         sharpCols row = map fst (filter ((=='#') . snd) (addColNr row))
>         withRowNr = zip [0..height-1] (map sharpCols pic)
>         addRowNr (rnr,cols) = zip (repeat rnr) cols
>    in
>         ( width, height, concatMap addRowNr withRowNr )

where sharpCols is the tricky one:  add column numbers to the row,
then filter it, retaining only the ones with '#' as the second
("snd") member of the pair, then return a list that consists only
of the first ("fst") member of each of those pairs.  There's
probably some Prelude library function to simplify this further,
but I couldn't find one.  And now, we have partial application
(=='#'), composition (. snd), and passing functions as arguments
to other functions.

That exercise finally made me think up this very straightforward
version of the first half of the problem.  I think it's clearer
than the listcomp version.  And it uses partial application:

> dal3MkPic :: Int -> Int -> [(Int, Int)] -> Picture
> dal3MkPic width height dotLocs =
>      let  sym r c = if  elem (r, c) dotLocs  then '#' else '.'
>           row r = map (sym r) [0..width-1]
>      in map row [0..height-1]


And there's some testing code ... passing functions to other
functions is really a big help when writing little tests.

> testfs mk mkNam rep repNam = do
>            putStrLn ("Try " ++ mkNam ++ " 7 5 [(1, 3), (3, 2)]:")
>            mapM putStrLn (mk 7 5 [(1, 3), (3, 2)])
>            putStrLn ("Try " ++ repNam ++ "( " ++ mkNam ++ " 7 5 [(1, 3), (3, 2)] ):")
>            prep <- return (rep (mk 7 5 [(1, 3), (3, 2)] ))
>            psho <- return (show prep)
>            putStrLn psho
>
> test = do
>            testfs makePicture "makePicture" pictureRep "pictureRep"
>            putStrLn ""
>            putStrLn "Now try Gunter's version"
>            testfs makePicture "makePicture" gunterRep "gunterRep"
>            putStrLn ""
>            putStrLn "Now try Doug's 'dal' versions:"
>            testfs dalMkPic "dalMkPic" dalRep "dalRep"
>            putStrLn ""
>            putStrLn "Doug's 'dal' version with dal2Rep:"
>            testfs dalMkPic "dalMkPic" dal2Rep "dal2Rep"
>            putStrLn ""
>            putStrLn "Finally, try Doug's 'dal3' versions:"
>            testfs dal3MkPic "dal3MkPic" dal3Rep "dal3Rep"