On Sat, Dec 6, 2008 at 3:39 PM, Dmitri O.Kondratiev
Daniel, thanks! I used your advice, it works, yet some more questions, if you don't mind :) So: {-- Why showList returns a function of type: type ShowS = String -> String In fact showList returns a function which already contains all values from list converted to a single string. Why return function instead of a ready to use string? --}
ShowS is for efficiency; consider evaluating this: ( ( ( "1" ++ "2" ) ++ "3" ) ++ "4" ) ++ "5" ("1" ++ "2") evaluates to "12", allocating 1 list cell ("12" ++ "3") evalutes to "123", allocating 2 list cells ("123" ++ "4") evaluates to "1234", allocating 3 list cells ("1234" ++ "5") evaluates to "12345", allocating 4 list cells In general, n left-recursive applications of ++ take O(n^2) time and space. Now, instead, if you represent each string as a function which concatenates itself with its argument, you end up with this: ( '1': ), ( '2': ), etc. You can then "concatenate" these functions via function composition: ( ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) . ( '4': ) ) . ( '5': ) This is already in normal form; but watch what happens when we apply it to []: ( ( ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) . ( '4': ) ) . ( '5': ) ) "" => ( ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) . ( '4': ) ) "5" , allocating 1 cons cell => ( ( ( '1': ) . ( '2':) ) . ( '3': ) ) "45", allocating 1 cons cell => ( ( '1': ) . ( '2':) ) "345", allocating 1 cons cell => ( '1': ) "2345", allocating 1 cons cell => "12345", allocating 1 cons cell This has allocations and time *linear* in the number of function compositions.
*ShowFleet> t2 fleet "Ship \"HMS Fly\" is a \"sloop\" with 16 cannons <*> Ship \"HMS Surprise\" is a \"frigate\" with 42 cannons <*> " *ShowFleet>
More questions: 1)Where characters \" come from in this case? 2)How showList function 'removes' characters \" from the output? What magic goes behind the scenes here?
1) They come from the "show" instance for String. Try "putStrLn (t2 fleet)" instead. 2) There's no magic; if the result at the ghci prompt is an instance of Show, it calls show and prints the result. In the first case, the result was a [Fleet], which is an instance of Show, so show is called, which (in the instance (Show a => Show [a])) calls showList from Show Fleet, and prints the result. In the second case, you are evaluating a String; then showList from Show Char gives you the representation. It's the same as this: ghci> [1,2,3] [1,2,3] ghci> show [1,2,3] "[1,2,3]" ghci> "hello\nworld\n" "hello\nworld\n" ghci> putStr "hello\nworld\n" hello world -- ryan