[Haskell-beginners] How to understand the type "ShowS"?

[Rustom Mody]

On Tue, Sep 24, 2013 at 3:45 PM, yi lu <zhiwudazhanjiangshi at gmail.com>wrote:

> Prelude> :i ShowS
> type ShowS = String -> String     -- Defined in `GHC.Show'
>
> It is a type of a function? I cannot understand this type, and don't know
> how to create functions of this type.
>
> And this function "shows"
>
> Prelude> :i shows
> shows :: Show a => a -> ShowS     -- Defined in `GHC.Show'
>
> I don't know how this function works.
>
>
Just attempting to give an imperative programmer's motivation for shows.

Look at the picture at start of http://en.wikipedia.org/wiki/Linked_list
which corresponds to the Haskell list
a = [12,19,37]
and 'a' would be a pointer pointing to the 12-node.

Now if we wanted to add something -- say 8 -- before 12, its a simple
operation:
Make a new node containing 8,
point it to the 12-node
Assign a to this new node [Remember we are in imperative-land!!]

This is a simple or constant-time operation

However adding something to the end is harder: we have to start from a and
walk down the list till the end and then mutate it to the new 8-node -- an
O(n) operation where n is the length of the list.

How can we have an O(1) add_to_end operation?

Well in imperative land there are many approaches, one of which is that for
every list like a, we also store an a_end pointing to the last element of a
and then mutate that.  This converts an O(n) operation into an O(1)
operation at the cost of a mere extra pointer.

shows is the same idea in FP-land!

The haskell list a = [12,19,37] is as you surely know
a = 12 : (19 : (37: []))
Replace the [] all the way in with an x and to make it valid lambda-bind
it; ie
a = \ x -> 12 : (19 : (37 : x))

a :: [Int] -> [Int]
If the Int were Char that would be the Shows type

And that lambda-exp basically constitutes your 'pointer-to-the-end'
In particular with normal lists
[12,19,37] ++ some_list
needs 3 steps to walk down the first list
However instead of [12,19,37] if we have the lambda-exp 'a' above we just
need to do

a some_list

and we have append being done by a single beta reduction step! Voila!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130925/403a52e7/attachment.htm>