Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the showS trick in Haskell?

Tags:

haskell

I have seen references to the showS trick to build strings (e.g., in this discussion), but I have never seen a good description of it.

What is the showS trick?

like image 523
luispedro Avatar asked Feb 08 '12 16:02

luispedro


People also ask

How does show work Haskell?

The shows functions return a function that prepends the output String to an existing String . This allows constant-time concatenation of results using function composition.

What does -> mean in Haskell?

(->) is often called the "function arrow" or "function type constructor", and while it does have some special syntax, there's not that much special about it. It's essentially an infix type operator. Give it two types, and it gives you the type of functions between those types.

What does ++ do Haskell?

The ++ operator is the list concatenation operator which takes two lists as operands and "combine" them into a single list.

Does Haskell use call by name?

Call by needHaskell is a well-known language that uses call-by-need evaluation.


2 Answers

In the standard library, ShowS is defined as:

type ShowS = String -> String 

This is a difference list. The trick is that a string xs is represented as a ShowS by the function that prepends it to any other list: (xs ++). This allows efficient concatenation, avoiding the problems of nested left-associative concatenation (i.e. ((as ++ bs) ++ cs) ++ ds). For example:

hello = ("hello" ++) world = ("world" ++)  -- We can "concatenate" ShowS values simply by composing them: helloworld = hello . world  -- and turn them into Strings by passing them an empty list: helloworld' = helloworld "" 

It's called ShowS because it's used in the implementation of the standard Show typeclass to allow efficient showing of large, deeply-nested structures; as well as show, you can implement showsPrec, which has the type:

showsPrec :: (Show a) => Int -> a -> ShowS 

This allows handling of operator precedence, and returns a ShowS value. The standard instances implement this instead of show for efficiency; show a is then defined in terms of it, as showsPrec 0 a "". (This default definition is in the Show typeclass itself, so you can just implement showsPrec for a complete instance.)

like image 76
ehird Avatar answered Sep 19 '22 23:09

ehird


showS uses the difference list approach to efficiently concatenate individual components of the shown value. The function takes the value to be shown, and a string to append to the result. The appended string is passed all the way down to the right-most sub-value until it reaches a leaf, where it is actually appended.

There's a description of difference lists (including showS) here http://www.haskell.org/haskellwiki/Difference_list

like image 38
pat Avatar answered Sep 20 '22 23:09

pat