On Sat, Dec 6, 2008 at 3:39 PM, Dmitri O.Kondratiev <[EMAIL PROTECTED]> wrote:
> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
