Learning-Haskell-Notes


1. Materials;  good tutorial for intro, good report for language specialists, 
but little in between for a "jobbing prgrammer".  

cf. "C++ annotated ref."  -- when I was learning C++, this book was 
invaluable for me, as it contained just the right mix of formal 
definition and in-depth pedagogical material.  I find the Haskell report 
tends to concentrate largely on definition, and skimps on explanation.
This would be fine, but the other more tutorial sources I consulted 
don't seem to have complete coverage of the language.


2. Error messages from compilers ... 
can sometimes be very obscure, misleading even.  
Especially in the realm of types and classes.


3. The type system is very subtle.  Maybe unavoidable.  cf 2.
I think that because so many concepts are separated, it's easy 
to focus on the wrong aspects of one's type declarations.


4. Multi-parameter classes are pretty much essential for many 
sizeable tasks or re-targetable software components.
More accessible documentation in this area would help.
(Thanks Oleg@pobox for helping me out here).

[Later] I note others, too, have observed the importance of 
multi-parameter classes.

Also, there is a need to be clear that multiparameter classes are 
general relational constraints.  I got locked into an incorrect 
reading that 'C a s' meant that 'a s' was an instance of 'C',
rather than C is a relation on types, of which (a,s) is a member.
It's not clear why I made this mistake -- I think the seeds of my
confusion may have been laid by the form of subclass declarations:
   (C a) => (D a)
means 'D' is a subclass of 'C', or 'a' stands for an instance of 'C' 
as well as 'D'.  In OO programming, classes are types and instances
are values -- Haskell separates these more carefully.
I don't know if this was just a personal confusion, or more widely 
experienced.   I know it's all explained, but it's difficult to take 
on all the new material at once without relying on some previous
experience.


5. It can be difficult to distinguish between simple typos and
deep abuse of the type system.  In this example:

	class (Eq k, Show k) => LookupEntryClass a k v where
	    entryKey :: a -> k
	    entryVal :: a -> v
	    newEntry :: (k,v) -> a
	data (LookupEntryClass a k v) => LookupMap a k v = LookupMap [a k v]

the error message reported (by HUGS) was of an invalid type constructor 
in the 'data' declaration, when the real problem was missing type 
parameters in the 'class' declaration;  i.e. should have been:

	class (Eq k, Show k) => LookupEntryClass a k v where
	    entryKey :: a k v -> k
	    entryVal :: a k v -> v
	    newEntry :: (k,v) -> a k v
	data (LookupEntryClass a k v) => LookupMap a k v = LookupMap [a k v]

(See also item 14 below, where I think I've finally figured out how
to make the class system dance for me.)


6. Monads can be a source of confusion.  The basic ideas are easy enough 
to get hold of, and using existing monad-based libraries is quite simple,
but the deeper issues of when and when not to use monads are less well 
covered.  Also, I found little help given on how to design new monads.
(Maybe this is covered, but if so it's not clear where to find the
appropriate material.  I found the paper "State in Haskell" by SPJ and 
John Launchbury to be one of the more helpful sources in this respect.
(The introductory approach of introducing IO first, then generalizing
to state (as in, say, "The Craft of FP") I found to be less helpful
in this respect.)


7. Programming idioms:  I suspect that even though I am now able to 
write Haskell programs of moderate complexity, I am not really using
the functional idioms as effectively as I might.  E.g. I have read 
claims that FP allows for better modularization of code, but I've 
found my own attempts to modularize seem to run into difficulties;
I guess I'm probably trying to apply conventional techniques 
inappropriately?  What is a good source of information about effective
programming style and idioms in Haskell?
[cf. Hughes' "Why FP matters" paper.]
[cf. "Scrap your boilerplate" paper.]


8. Functors:  I kept on bumping into this idea of a "functor" without
any real motivation.  Then suddenly it seemed to click... A "functor" is a
structured collection (or container) type with a method that accepts a
function and applies it to the members of the collection yielding an
similarly structured collection of values of a (possibly) new type. 
Is this right?  If so, it doesn't seem to be expressed clearly anywhere 
that I've come across yet.


9. Monad composition.  Reading the material, I found this really confusing.
Not because it's difficult, but because the patterns used are so different
from what I'm used to in conventional programming.  The particular area 
that I was having problems getting my head around was the undertsanding
how the monad type was created, and how final values are used.  Many of the
examples I found appeared to gloss over these issues, expecially if some
result was to be used in a non-monadic expression.  I think a cookbook
approach to use composed monads, with emphasis on actually how to actually
execute the monads and extract a final result, might be helpful.
Eventually, I found Mark Carroll's example in
http://www.haskell.org/hawiki/MonadState to be really useful.  I spent a
little while adding comments to this example, and everything became much
clearer.


10. Type classes, class constraints and data declarations.  
Try to avoid putting class constraints on data declarations.
I found myself doing this when declaring a datatype intended to be an
instance of a particular class, and then finding the type system would 
not allow me to make it a member of some other class, such as Functor,
because the constraint was not justifiable by the method signature for 
that class.  I think this is an artefact caused by OO-style thinking:
"an instance of this class must be subject to the class constraints".
The data type used as an instance need not (and, it seems, usually 
should not) be subject to the class constraints.  The data type may still 
be used for non-class purpose, and this is assumed when it is used as
an instance of some other class, like Functor.  It's only when the
specific class methods are applied that the constraints come into play.


11. A common error leading to really obscure error messages:

      return f a

in a do-sequence, instead of:

      return $ f a

Compilers might helpfully notice this and offer a hint.  
I can't think of any situation when the former case is actually sensible.


12.  Type classes are not as useful as they first seem.  Or, maybe more
correctly, there are many better ways to achieve the same things that
an OO programmer would do using classes (or, in Java, interfaces).
I find that I declare a class, and instances of that class, and other
functions and structures that use that class, and down the line I find
it really doesn't do what I want to do because I find I cannot mix
different instances of the class in the way I'd like.  E.g. a list of 
class instances must have values of the same instance in every position.
Generally, it looks as if storing instances of a class in a structure
is often the wrong thing to do, unless it is truly required that the
various values are fully interchangeable and mixable.  
The other way is to use polymorphic function types:  if the putative
class has just oneinterface method, consider declaring a function type
instead, and using that.  If there are several methods, declare an 
algebraic data type whose members are polymorphic functions.

The time to use a class seems to be when there is a genuine desire
to instantiate a particular interface over different and specific 
underlying types of data.  A class doesn't make so much sense as 
a structuring or organizing mechanism.


13.  Existential types

I think that 'forall x' introduces x as existential when it appears 
immediately preceding a datatype constructor declaration.
Elsewhere, it appears to signal a universal quantifier.

Existential types are a kind of information hiding mechenism:
some datatype is used in an implementation, but its details are 
hidden from view, and the particular type used may vary from 
instance-to-instance in the same surrounding type context
(e.g. between members of a lit).  Having the existential type
being an instance of a class may provide means for some functions
to do useful things with the type.

[cf. discussion of issues on Haskell-cafe mailing list, 
about October 2003.]


14.  More on type class subtleties; class dependencies

I think I finally figured out how to get my LookupMap abtraction to
work the way I wanted.  The idea was that I would be able to use
LookupMap to provide a lookup over any datatype by creating an
appropriatre LookupEntryClass instance decloaration.  Originally,
I had:
    class (Eq k, Show k) => LookupEntryClass a k v
        where
            newEntry    :: (k,v) -> a k v
            keyVal      :: a k v -> (k,v)
and
    instance (Eq k, Show k) => LookupEntryClass (,) k v where
        newEntry = id
        keyVal   = id
and
    data LookupMap a k v = LookupMap [a k v]

(A list is a poor implementation structure for this purpose.  
The idea of this class is that I can vary the implementation
while maintaining a consistent interface for my applications.)

The trouble with this is that I couldn't use an existing type
as a lookup entry unless it had a type constructor was of the 
prescribed form;  i.e. (typename keytype valuetype) in this case.
I finally realized, after 6 months or so of using Haskell, that I 
could declare the lookup entry class thus:
    class (Eq k, Show k) => LookupEntryClass a k v | a -> k, a -> v
        where
            newEntry    :: (k,v) -> a
            keyVal      :: a -> (k,v)
and
    instance (Eq k, Show k) => LookupEntryClass (k,v) k v where
        newEntry = id
        keyVal   = id
and
    data LookupMap a = LookupMap [a]

That is, the LookupEntryClass constructor takes three parameters of 
kind *, rather than the first being of kind * -> * -> *.  In this way,
the way that the component types are related to the lookup entry type
is hidden.  The downside of this is that the system can no longer infer
that if, say, a k v is a LookupEntryClass then so is a v k.  There is
also some other type information that was inferred automatically but
which now must be stated explicitly.

When needed, the key and value types are made available through a 
context declaration, ala:
    keyOrder :: (LookupEntryClass a k v, Ord k)
        =>  a -> a -> Ordering
    keyOrder e1 e2 = compare k1 k2
        where
            (k1,_) = keyVal e1
            (k2,_) = keyVal e2

I don't think this approach would be possible without using the type 
class dependency extension to Haskell.


15. Using ShowS

ShowS is a type that is used to improve the efficiency of creating 
long strings (character sequences) that are for output, or are 
otherwise used in left-to-right order.  

The problem addressed by ShowS is that string concatenation is O(n) in the
length of its first string argument:  this means that when building a 
long string by successive concatenation, the time required to append
each character is proportional to the length of the string, making the 
overall time requiired to build the string equal to the square of its 
length.

Type ShowS is defined as:

    type ShowS = String -> String

At first glance, ShowS does not appear to rectify this, since a ShowS 
for a string value is defined simply as (++):

    showString :: String -> ShowS 
    showString = (++)

ShowS uses lazy evaluation to defer evaluation of the ++ operation;  if the string 
is accessed strictly sequentially, it never needs to be evaluated.
Consider the expression:

    a ++ b

In order to access the first character of the resulting string, it is necessary to 
evaluate 'a'.  If 'a' itself is a concatenation of strings:

    (a1 ++ a2) ++ b

then that concatenation too must be evaluated.

By representing an unterminated string as a function, the evaluation of
concatenation can never be required until the string is closed, by applying
the ShowS function to en empty string (or any string).  
The above example then would be:

    showString a1 (showString a2 (showString b ""))

Thus, the introduction of a function allows the left-associated 
construction of concatenations to be evaluated in a right-associated
fashion.  To get at the start of a sequence, it if not necessary
to evaluate anything that comes after it.

So how should one use ShowS values:  there are three key operations:

(1) to turn a string into a ShowS, use showString.  Or just a section:

      a = showString "Hello"
    or
      a = ("Hello"++)

The Haskell prelude and library provide functions that turn other values
into ShowS:  the default mechanism is to turn them into a string, then 
apply showString as above.  The default showsPrec is defined as:

    showsPrec _ x s = show x ++ s

which might equally be written as:

    showsPrec _ x = (show x ++)

or

    showsPrec _ x = showString (show x)

When implementing complex data structures as instances of Show, 
consider implementing showsPrec instead of show.

(2) to turn a ShowS into a string:  simply apply it to an empty string:

    a = \x->"Hello"++(" world"++x) ""
      = "Hello"++(" world"++"")
      = "Hello"++(" world")
      = "Hello world"

(3) to concatenate ShowS values, use function composition:

    (a . (b . c)) x = a ((b . c) x)
                    = a (b (c x))

    ((a . b) . c) x = (a . b) (c x)
                    = a (b (c x))

So if:

    a = ("Hello,"++)
    b = (" cruel"++)
    c = (" world"++)

    (a . b . c) "" = a (b (c ""))
                   = a (b " world")
                   = a " cruel world"
                   = "Hello, cruel world"


16. Use standard types as far as possible

There is extensive support for doing useful things with the standard 
types declared in the prelude.

For example, it may be tempting to define a new type to represent a
particular value or absence of a value ... I initially did this for my 
RDF language tags, defining:
   data Language = Lang String | NoLanguage

It would have been far better to use:
   type Language = Maybe String

Many of the built-in types are defined as Monads or Functors, either in 
the prelude or in supporting libraries.  While not obvious to someone 
new to Haskell, these additional definitions provide a rich seam of
added functionality, ready to be accessed as the techniques associated 
with higher order become appreciated.


17. The power of 'sequence'

The prelude function 'sequence' is surprisingly versatile.

The basic type signature:
   sequence :: Monad m => [m a] -> m [a]

Its function varies with the kind of Monad (m) with which it is used:

list: sequence has the effect of computing a cartesian product

Maybe: sequence returns Nothing if any of the list members is Nothing,
       otherwise Just a list of bare values.

Error monad: returns the first error in the list, or a list of values
       if there are no errors

State monad:  returns the effect of applying each transformation in turn.

IO: (also sequence_) returns a new IO monad that is the result of 
    executing each of the statements in turn.  One particular use for 
    this is to turn a series of IO monads each returning some value 
    into a single IO monad that returns a list of that value.

Sometimes, sequence can be applied more than once to a value, with 
each application having quite different effects.


18.  ((->) e) is a Monad

It is the simplest(?) instance of a Reader Monan, which can be used
to allow several functions to be evalated against the same 
"environment" value.