On Tue, Sep 24, 2013 at 3:45 PM, yi lu <zhiwudazhanjiangshi@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!