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