Blogs

I'm at a crossroads in my Haskell study

Submitted by metaperl on Thu, 11/30/2006 - 11:21am.

Chapter 7 in SJT is "Defining functions over lists" --- this is arguably the meat-and-potatoes chapter of the entire book, and it has some great exercises.

However, I was a bit concerned with the given implementation of split because it went over the same part of the list twice:

split :: String -> [Word]
split [] = []
split st
  = (getWord st) : split (dropSpace (dropWord st))
which lead me to examining the source in the Haskell prelude

It looks interesting. So I'm pondering whether to study the entire prelude or continue on with the text.

I think the book is better for me, so that I can learn more of the Haskell system - modules, type classes, infinite lists, monads, algorithm analysis.

It will make me a complete programmer, ready for other interesting articles and exercises and contributions to the Haskell community.

A very nice short monad tutorial

Submitted by metaperl on Thu, 11/30/2006 - 3:17am.

exists right here
... I like how he partitioned the idea of monads into 3 types. I wonder why Cale wrote "Monads as Containers"... was he trying to say that was the only way to look at them? Or must a container always be present? I'll have to ping him on that.

Metacognitive processes involved in deriving a solution to unzip

Submitted by metaperl on Wed, 11/29/2006 - 1:10pm.
Writing my own implementation of unzip was difficult.

This morning I began to think that working top-down was not the best idea. Or perhaps that working both top-down and bottom-up is best... let's see.

First, let's apply our every-useful top-down tools for problem solving - typing, cases, pictures and induction step.

Let's start with typing unzip:

      unzip :: [(a, b)] -> ([a], [b])
    
Ok, great, so we are getting in a list of 2-tuples and want to convert that into a 2-tuple in each element tuple element is a list. Let's continue with some easy cases:
      unzip [] = ([].[])
    
Ok, how about a picture of a non-trivial case:
      unzip [(1,4),(2,5),(3,6)] = ([1,2,3], [4,5,6])
    
Hmm, the first thing that I see is the tuple
(1,4)
has been broken out into the first elements of the output list. Let's give an algebraic expression of that:
      unzip (x:xs) = ( fst x : xs_fst , snd x : xs_snd )
    
Cool, I love it! Now we only need specify how to get
xs_fst
and
xs_snd
. Hmm... well, let's take a more trivial but nonetheless non-trivial case:
      unzip [(1,4)] = ([1], [4])
    
Now in this case, what do
xs_fst
and
xs_snd
look like? That's right, they are empty lists, which means our trivial case applies. In other words, in this case:
      (xs_fst, xs_snd) = unzip([])
    
Which means:
      unzip [(1,4)]    = (1 : xs_fst, 4 : xs_snd)      
        where 
           (xs_fst, xs_snd) = unzip xs -- Since xs == []
    

an entirely different approach

Lock in the base case

      unzip [] = ([].[])
    

Rewrite your type signature using the base case whenever possible

Sounds odd, but let's do it:
      unzip :: [(a, b)] -> ([a], [b])
      unzip [(a, b)] = ([a], [b])   -- this is true for a 1-elem input list
      unzip  (a, b) : []  = (a : [], b : []) -- rewrite in cons notation
      unzip ((a, b) : xs) = (a : a', b : b') -- this generally true! done!
        where (a', b') = unzip xs
    

The only reality is the present moment - state retention is delusion

Submitted by metaperl on Wed, 11/29/2006 - 10:52am.

I do quite a bit of spiritual search in my freetime. And for the longest, I have been bitten by this idea over and over, so now I will express it. And this is not my idea, you can read Eckhart Tolle, "The Power of NOW" or listen to any Advaita Vedanta teacher and they will tell you:


the only thing that is real is the present moment.

your thoughts about the present moment are attempts to conceptualize and relate this moment to other stored concepts and relations. This is what is known as understanding. It is not knowledge, but rather mental comprehension.

Also, Repeatings and recordings via memory are only real when they are brought into the present moment. all of Which means everything which ever happened and everything that ever will happen will happen in the NOW.

So what? Well, Haskell, being a purely functional language is all about NOW. It is one of the few languages which makes a concerted effort to have all statements about past and future effects cleanly, correctly and completely and explicitly described from the standpoint of the Ever Present Presence.

:: steps down from soapbox ::

Suggested HApps examples

Submitted by metaperl on Wed, 11/29/2006 - 9:22am.

Happs is a great web kit for haskell, but a a recent thread in the mailing list shows that it needs examples. Here is a good set of starters:

example1: the simple one-liner that serves static files
(with example static files to serve)

example2: adds to example 1 some simple state
(for example a counter)

example3: adds a request handler that displays
a dynamically-generated page that
displays the state

example4: adds an input and a handler that can
be used to change the state

...and so on, for savers, sessions, etc.

Each example would reuse the code from the previous one, so that notes
could highlight the changes, and explain their motivation.

-- credit to Mikel Evins for the example list

Python Decorators - not desirable in Haskell

Submitted by metaperl on Wed, 11/29/2006 - 2:08am.

This is not a planned out post, but I feel the need to compare Python decorators with The Haskell Way.

I recently read Philip J. Eby's article on decorators and it was eye-opening.
Let's see first what the purpose and definition of a Python decorator is before comparing them with The Haskell Way.

PURPOSE
Philip says that one use of decorators is to reduce code duplication. For example if a set of methods needs to be wrapped for additional functionality, such as synchronization, pre/post conditions, etc, then you can simply annotate each with the appropriate decorators.

The second use is to have the meta-information about functions right with the function so that the data is never out of sync with the function. Then you can locate all methods with certain characteristics via the decorator API (I suppose)

DEFINITION

I don't know why it took Phillip to the middle of the paper to define a decorator, but I think it was a good move... to sort of whet your appetite before giving you the definition. After all, this is not a mathematical proof. Anyway, a decorator is "...a callable object (like a function) that accepts one argument—the function being decorated. The return value of the decorator replaces the original function definition."

Comparison with Haskell
The very first thing that comes to mind is decorating destroys manifest interface. You can no longer examine a piece of code and examine the type signature of the functions it calls and know what is supposed to happen.

Haskell employs an entirely different approach to modifying function behavior. If you have a stereotyped way of modifying a set of functions, you would have to call the modifying function not call the original decorated function.

This is actually more flexible and composeable - the original function does one thing simply and clearly, then any combination of control strategies can be layered on top via other functions.

Let's take each of Philip's purported purposes of Python Decorators and see how Haskell accomplishes the same thing, but with that unmatched Haskell-esque elegance, flair, power and control. Yes, that's right, all 4 terms apply: elegance, flair, power and control:

CODE DUPLICATION
Well, that's what functions are for. If there is a list of things that need to be done to a function, then that itself is another function taking the first function as an argument.

The additional power of The Haskell Way is that you are not tied down to decorating a single function in a single way... for example: is it really the case that you should be decorating the division of two numbers with an exception? What happens when you want to decorate it with something to generate HTML instead?

SCATTTERING OF KNOWLEDGE
Phillip says that sometimes "...a framework needs to be able to locate all of a program's functions or methods that have a particular characteristic, such as 'all of the remote methods accessible to users with authorization X.'"

But I dont know about that. When was the last time I needed this sort of information? If so, is seat-of-the-pants annotation the way go? Why not use Template haskell to generate all such methods ahead of time?

CONCLUSION

Decorators do not belong in Haskell. They rob a language of referential transparency. They result in "pull-style" programming as opposed to injecting control.

Parser with Writer monad

Submitted by jmuk on Wed, 11/29/2006 - 1:07am.
::

I tried to write a parser for bencode format. Bencode is normally used in BitTorrent only, but can be used for generally purpose.

In order to write the parser with parser combinators libraries such as Parsec, I encounter a problem. I applied Packrat Parsing to JSON parser, but I may use a sledge hummer to kill a fly. JSON is a simple format, it is very easy to parse with normal string-related functions. Packrat Parsing is too strong mechanism.

However, my point is not power of parser library, but memory copying. Normally, the parse result is copied from the original text by parser library. On the other hand, ByteString head, tail, init, last, take, drop, and similar functions do not copy any text data, but just modifies the offset and length of the text. If the parsed data has many text data, the parser must do the memory copy that is not potentially required.

The parser combinator library that does this is a challengeable task -- but, here I applies a small approach to parse bencode format. See http://darcs.haskell.org/SoC/haskellnet/Text/Bencode.hs

Here, all parsers are Writer monad.
Writer monad does `Computations which produce a stream of data in addition to the computed values' (came from All about monads). In parser context, `a stream' corresponds to the parsed result, and the computed value to rest of text.

We can easily combines the parser for `list of nodes' or `dictionary of nodes', using a function untilM :: (a -> Bool) -> (a -> m a) -> a -> m a.

It is true that this simplest approach lacks some important features. For example, this parser do not contains line and character information, which means that the parse error cannot print appropriate debug info. In despite of such fault, this parser works well for our purpose. Debug information will be the next step.
BTW, debug info is not a serious problem for bencode parser, because this format is not human-readable. In such case, the required information is whether the format is valid or not.

Tools for haskell problem solving

Submitted by metaperl on Tue, 11/28/2006 - 6:43pm.

TYPING
This is your very first tool. Write out the type for the function that will solve your problem.

CASES
Write down your trivial base cases

INDUCTION STEP
You wrote down your accurate base case. Now imagine your function having to process an input data set with just one element more than your base case.

Then, write out that case algebraically

PICTURES OF DATA FLOW
Cale Gibbard has some nice pictures of how data can flow through functions when using foldl. And the technique is applicable elsewhere.

One job title you will never see - Junior Haskell Developer

Submitted by metaperl on Thu, 11/23/2006 - 2:19pm.

I am a Senior-level Perl developer with 6 years of corporate experience.

I managed to eek my way to this lofty status by imitation. I bought lots and lots of Perl journals, read lots and lots of code, chatted in IRC channels, read perlmonks.org religiously and basically became capable of aping an answer to anythiing at anytime.

Oh and CPAN modules helped a lot because I only needed to follow directions and they cover almost any corporate scenario one might have.

So, at one time I was a junior sponge and now I am a senior sponge. I am not more intelligent I just have more idioms under my belt and can crack them off almost unconsciously.

Flip to Haskell. I have tried this approach to learning Haskell 2 or 3 times and each time I had to call the paramedics for oxygen. There is no such thing as a Junior Haskell Programmer.

You either possess the ability to conceptualize the functional decomposition of a problem or you get NOTHING done.

Haskell is a very exacting discipline and you either Master it or remain a fool and the only difference between the two is how much time you put into gaining a grasp on the power, scope, elegance and techniques for wielding the 3-fold synergy of strong typing, lazy evaluation, and purely functional application.

As a side note, I am of course wise enough to be dropping Perl for Python. And even though it is not Haskell, it is worlds better for 90 million reasons I wont go into right now.

Research idea - mapping haskell type signatures to real world questions

Submitted by metaperl on Tue, 11/21/2006 - 5:08pm.

Hoogle is sort of what I'm thinking about. But Hoggle requires well-typed info to find the functions you are looking for. And hoogle does not string together functions into solutions or programs.

In #haskell, all day long, there is question after question such as "How can I get a list of all pairs from this list" or "how do I apply a function to the first element of a list and then take that result and apply it to the next element of the list?"

Can we take the next step from hoogle and take english language requests and turn that into haskell code?

Can we build a browser for Haskell functions that allows one to navigate a tree of semantic concepts?

Most importantly, can we get inside the head of a Haskell programmer and break down his solutions into easy steps to make it easier for others to learn haskell?