Recent Updates Toggle Comment Threads | Keyboard Shortcuts

  • igstan 9:41 am on March 11, 2010 Permalink | Reply
    Tags: Eric S. Raymond, , Lisp   

    On Learning Haskell, by Eric S. Raymond 

    I’ve just found a nice piece of text, written by Eric S. Raymond, in which he talks about his experiences with Haskell. In case you didn’t know, he’s the one who said the following about Lisp:

    LISP is worth learning for [..] the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.

    Apparently, he ends up with the same conclusion in his article, On Learning Haskell.

     
  • igstan 11:18 pm on January 16, 2010 Permalink | Reply
    Tags: big-o-notation, clever, exercise, recursive, trace   

    Mean of a list 

    In this post I’m going to dissect a solution to the mean of a list problem proposed as an exercise at the end of chapter 3 in Real World Haskell. The problem reads the following:

    Write a function that computes the mean of a list, i.e. the sum of all elements in the list divided by its length. (You may need to use the fromIntegral function to convert the length of the list from an integer into a floating point number.)

    I’ve tried to figure out a solution to this problem half a year ago, not long before I dropped the study of Haskell. The actual difficulty that I had wasn’t about how to solve it, but rather, how to solve it using only the functions presented up to that point in the book. Sure, you need a sum of all the numbers in the list, divided the the length of the list. I knew a length function was presented already in that chapter, but I didn’t remember about a sum function. Even after looking the previous chapters for sum, I couldn’t find it (but it was there). So, I said to myself that I should solve it without that particular function. Maybe the authors were up to teach me something, right?

    I, therefore, created my helper sum function that would do just that, return the sum of elements in a list. Things were working smoothly until I hit myself against the typeclasses wall. I had no idea what type to return… Double, Float, Fractional. Honestly, it’s still a mess in my head with regard to types and typeclasses. So I went to the online version of the book to solve this issue. There, I looked for comments regarding my problem and one of these solutions actually caught my eye, but not for the way it solved the return type issue. It was Rob Grainger’s solution that used nothing more than functions presented in the book up to that chapter (but not sum or length). Here’s his solution:

    mean :: [Double] -> Double
    mean l = snd (inner l) / fst (inner l)
             where inner []     = (0,0)
                   inner (x:xs) = (fst (inner xs) + 1, snd (inner xs) + x)

    This is brilliant. He, basically, created a helper function (inner) that would return both the sum of the elements in the list as well as the length of the list. All in a 2-tuple data structure. Then he would extract the two elements in the tuple using the built-in fst and snd functions, and ultimately apply the division function (/) on them.

    Now, the helper inner function is a recursive function that reduces the whole list of numbers to a 2-tuple of numbers. It starts from the first element in the list and uses this element for two purposes:

    1. increment a counter of the elements in the list
    2. add it to the second element in the tuple, which is the sum of elements in the list

    For clarification, a list comprising of only three elements, [1, 2, 3], would generate the following execution trace:

    inner [1, 2, 3]
        == (fst (inner [2, 3]) + 1, snd (inner [2, 3]) + 1)
        == (fst (fst (inner [3]) + 1, snd (inner [3]) + 2) + 1, snd (fst (inner [3]) + 1, snd (inner [3]) + 2) + 1)
        == (fst (fst (fst (inner []) + 1, snd (inner []) + 3) + 1, snd (fst (inner []) + 1, snd (inner []) + 3) + 2) + 1, snd (fst (fst (inner []) + 1, snd (inner []) + 3) + 1, snd (fst (inner []) + 1, snd (inner []) + 3) + 2) + 1)
        == (fst (fst (fst (0,0) + 1, snd (0,0) + 3) + 1, snd (fst (0,0) + 1, snd (0,0) + 3) + 2) + 1, snd (fst (fst (0,0) + 1, snd (0,0) + 3) + 1, snd (fst (0,0) + 1, snd (0,0) + 3) + 2) + 1)
        == (fst (fst (0 + 1, 0 + 3) + 1, snd (0 + 1, 0 + 3) + 2) + 1, snd (fst (0 + 1, 0 + 3) + 1, snd (0 + 1, 0 + 3) + 2) + 1)
        == (fst (fst (1, 3) + 1, snd (1, 3) + 2) + 1, snd (fst (1, 3) + 1, snd (1, 3) + 2) + 1)
        == (fst (1 + 1, 3 + 2) + 1, snd (1 + 1, 3 + 2) + 1)
        == (fst (2, 5) + 1, snd (2, 5) + 1)
        == (2 + 1, 5 + 1)
        == (3, 6)
    

    Or, using some ASCII art, the execution tree would look along these lines (I have represented only the arguments that inner would receive for each application):

            [1,2,3]
             /   \
            /     \
           /       \
       [2,3]        [2,3]
        / \          / \
       /   \        /   \
     [3]   [3]    [3]   [3]
     / \   / \    / \   / \
    [] [] [] []  [] [] [] []
    

    As you can see, there’s a lot happening in there for such a small input list. The main reason is that, for every element in the list, the inner function is executed twice. It is doubly recursive, which, if I’m not wrong, it means the solution has a complexity of O(n2)? Honestly, big O notation is not my strong point, so I may be wrong about this.

     
  • igstan 9:01 pm on January 16, 2010 Permalink | Reply
    Tags: start-over   

    I’ve come back 

    After half an year of absence, I’ve returned to my quest of learning Haskell. The time was short, the projects were many and I didn’t succeed in finishing the basics of Haskell. But I also didn’t forget about this project of mine, so I came back. I hope this new attempt will be much more fruitful. So, back to learning.

     
  • igstan 11:12 pm on July 23, 2009 Permalink | Reply
    Tags: binary-operator, minus-operator, unary-operator   

    The minus operator in Haskell 

    In a previous post, concerning the two ways Haskell does function application, I was using as examples arithmetic operations. Among other things I said (I actually cited from Real World Haskell) that the minus (-) operator is Haskell’s only unary operator. I also said that it looks wrong to me, but I was wrong in fact. According to the Haskell 98 report, the operators section, the syntax -x, where x is a number, is a special form and it is indeed the only prefix (and unary) operator in Haskell. Additionally, the minus (-) function used in expressions of form x - y is actually the binary (it takes two arguments) function minus (-), about which we can find the type signature:

    Prelude> :t (-)
    (-) :: (Num a) => a -> a -> a
    

    The unary operator minus ((-)) has no relationship with the binary operator. It is actually an equivalent of the negate function. So, if we want to find the type signature of the minus (-) unary operator we must do:

    
    Prelude> :t negate
    negate :: (Num a) => a -> a
    

    Yay! I clarified yet another thing in my Haskell journey.

     
  • igstan 9:40 pm on July 23, 2009 Permalink | Reply
    Tags: function-application, functions, infix-notation, polish-notation, prefix-notation   

    Haskell’s prefix and infix notations 

    Like any other language out there, Haskell has possibility for basic arithmetic operations – addition, subtraction, multiplication, division. As I said in my prelude, there are languages in which these operations are represented by special operators and languages in which they are well respected citizens and have function status. Haskell is a gentleman and treats arithmetic operators as functions. This may seem weird at first if all of your experience is with main-stream languages like any of the C family of languages. In Lisp, having, let’s say + as a function, was easy (although it looked a little bit awkward at first) because its place wasn’t between the two arguments, but rather in front of them:

    ;; Lisp code
    ;; evaluates to 3
    (+ 1 2)

    Haskell employs a clever concept in order to have basic arithmetic operators as first class citizens (i.e. functions), while still allowing us to write code in a traditional manner, with the operator placed in between the operands:

    Prelude> 1 + 2
    3
    

    The cleverness I was talking about is that Haskell offers the possibility to call functions in two different notations:

    1. infix notation, the function is placed in between the arguments
    2. prefix or polish notation, what we’re used to with functions from main-stream languages

    Because of this possibility we can write our additions to use polish notation too, almost as in Lisp:

    Prelude> (+) 1 2
    3

    As you may have noticed, in this case, the function must be enclosed in parenthesis, for the convenience of the compiler I believe, but this is an exception from the rule. The normal rule states that functions used with the infix notation must be enclosed between two backtick characters.

    
    Prelude> let add a b = a + b
    Prelude> add 1 2
    3
    Prelude> 1 `add` 2
    3

    Under this new light, it makes perfect sense for arithmetic functions to not obey the standard rule for invoking functions using infix notation. Having to write 1 `+` 2 would be really awkward. Much more awkward than Lisp’s solution in my opinion.

    Special rules when using negative numbers

    Now, there’s one more thing to mention about Haskell’s arithmetic implementation. There is an issue with using negative numbers in compound calculations. Normally, in Haskell, a negative number is written as in any other language we know about. For example: -1.

    The minus operator is Haskell’s only unary arithmetic operator (or not?), i.e. it takes a single argument. Further more, it has the same level of precedence as the + function. Because of this precedence level, we can’t write:

    Prelude> 1 + -1
    
    <interactive>:1:0:
        precedence parsing error
            cannot mix `(+)' [infixl 6] and prefix `-' [infixl 6] in the same infix expression
    

    Having both an addition and a subtraction in the above code, Haskell does not know which of them to apply first. So we have to enclose the negative number in a couple of parenthesis:

    Prelude> 1 + (-1)
    0
    

    That was all for today’s infix and prefix/polish notation used for calling Haskell functions.

    References

    P.S. While writing this post I realized that the statement “The minus operator is Haskell’s only unary arithmetic operator”, which appears in Real World Haskell may be a little wrong. I’m going to write about this in a future post.

     
    • ray 11:25 pm on July 29, 2009 Permalink | Reply

      (+) being infix isn’t an exception to the rule – the rule is that a function whose name comprises “symbols” is an infix operator, and its name has to be surrounded in parentheses for the function to be used prefix, just like a regular function’s name has to be surrounded in backticks for it to be used infix. Unary minus is a special case, though.

  • igstan 3:48 pm on July 19, 2009 Permalink | Reply
    Tags: , motivation, Prelude   

    Prelude 

    The title of the first post isn’t accidental. Although I’ve recently decided to keep a blog with my progress in learning Haskell, I had a few contacts with the Haskell interpreter. For those who have no experience with the language, Prelude is a standard library of functions loaded when the interpreter is started. But it makes for a good first blog post name.

    Why learning a new language

    This is a question I see asked more and more. Honestly, I do it because I have an innate curiosity about how different programming languages look like, what kind of programming paradigms they support and what they offer, from a programmer point of view, compared to other languages. Almost two years ago, I started watching the MIT videos lectures for Structure and Interpretation of Computer Programs. I have managed to complete the whole series a year ago. Not that it would be a long series, but due to the lack of time. The important thing is that the lecturers used Lisp for teaching the actual concepts, and while I didn’t have the chance to use Lisp in the real world, those videos helped me to better understand a language I frequently work with, namely JavaScript, the world’s most misunderstood programming language. It made me better understand concepts like lambda, recursion, pattern matching and abstraction. From those lectures I found out that what we usually see as ordinary arithmetic operators, are actual functions. Those languages that do not implemented them as such, should reconsider their design.

    That’s why I want to learn a new language. I’m eager to unravel any new programming concept that lies deeply hidden in front of my eyes. It makes me a better programmer and it quenches an inexplicable thirst for knowledge that I have.

    Why learning Haskell

    I chose it for various reasons. Some of them may be childish, some of them not. From the childish category I can enumerate:

    • it has a very appealing name
    • it has an unusual syntax
    • there’s a small (read it select) group of individual knowing Haskell
    • what the heck are monads and why didn’t I know about them?
    • Simon Peyton-Jones is a nice guy (the man behind the Haskell compiler)
    • I’ve heard that The Haskell Cafe (Haskell’s mailing list) has nice folks too

    I’m not sure the latter two are that childish, as I, for one, hate places where people are talking down to me.

    From the list of more serious reasons for choosing Haskell, I can think of:

    • it has strong support for functional programming, a paradigm I have grown to appreciate
    • the language is born after years of committee discussions (not always a good thing though)
    • what the heck are monads and why didn’t I know about them?
    • it has strong roots in mathematics, not that I’m a fan of this discipline, but it’s nice to see that some of the more complex concepts are actually applicable in the real life

    Why this blog

    I don’t intend this blog to be a starting point for someone else who wants to learn Haskell. This is just my progress log in learning the language. I’ll try to write as often and as best as I can, just because trying to lay the concepts down will force me to better understand them. Also, the fact that someone else might come here and see what I have to say, obliges me to think twice before saying stupid things. This is the whole purpose of this blog, to better grasp Haskell. Nothing more.

    That’s pretty much all I can say for a first post, which is enough I guess. The rest of my posts will probably be course notes from the two sources that I’m using for the moment:

    As other sources will be used, I’ll mention them in the respective entries.

    Onwards and upwards!

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Follow

Get every new post delivered to your Inbox.