code golf - wordCount

An example for one of the courses taught here, was a program that counts the number of occurrences of unique words in a file. It was written in Python, and was clean and concise enough.

Following is a Haskell version:

import Control.Arrow((&&&))

import Data.List(group,sort)

wordCount :: String -> [(String,Int)]
wordCount = map (head &&& length)
          . group . sort . words

haskell - lack of debugging and stack tracing

Haskell is a wonderful language. It provides a great level of abstraction and a fruitful ground for programming languages research.

But it lacks some certain things that other environments naturally have, like advanced debugging tools or to the least stack traces. Since the evaluation of a haskell program is a bit strange, conventional techniques are not generally applicable.

I've seen this video however, and if they do manage to integrate the tool into GHC with a reasonable degree of robustness and reliability, I think Haskell will have a great stack tracing toolkit. Moreover, since it is a playground for CS geeks, the proposed system will provide another fruitful ground to hack around.

I quite liked the approach.



Finding the needle: Stack Traces for GHC
Tristan Allwood, Simon Peyton-Jones and Susan Eisenbach
Haskell Symposium
Edinburgh 2009
ACM SIGPLAN

RE: eve/did=.talktalktalk... - haskell is just as good

RE: http://ozgurakgun.blogspot.com/2010/04/evedidtalktalktalk.html

If you implement a simple algorithm usings haskell's list comprehensions, the performance turns out to be just as good. Of course the tools mentioned in the previous post are a) general purpose tools, b) would be far better in harder problems.

Anyway, the interesting part of the haskell code is the following:

evedidtalk =
    [
        [e,v,d,i,t,a,l,k] |
        e <- [1..9],
        v <- [0..9] \\ [e],
        d <- [1..9] \\ [e,v],
        i <- [0..9] \\ [e,v,d],
        t <- [0..9] \\ [e,v,d,i],
        a <- [0..9] \\ [e,v,d,i,t],
        l <- [0..9] \\ [e,v,d,i,t,a],
        k <- [0..9] \\ [e,v,d,i,t,a,l],
        digitsToInt [e,v,e] * 9999 ==
        digitsToInt [d,i,d] * digitsToInt [t,a,l,k]
    ]

Here, evedidtalk is a list of digits, that satisfy the only constraint we have. The key to performance is limiting the number of alternatives generated using the \\ (list difference) operator.
A poor-in-performance alternative would be generating all possibilities and then checking for the second constraint we had, the alldiff.

Compiled with -O2 using ghc, this finds the two possible solutions in under a second (yet, slightly slower than tailor+minion).

eve/did=.talktalktalk...

I've stumbled across this problem recently: http://www.jimloy.com/puzz/evedid.htm

It is very much like the SEND + MORE = MONEY problem, but I thought it would be more interesting (=harder to solve). Nope, not at all.

OK, the problem is the following:

Find the digits E,V,D,I,T,A,L,K such that this equation holds: EVE/DID=.TALKTALKTALK...
EVE and DID are 2 numbers with 3 digits each, and .TALKTALKTALK... is a floating point number.

After exploiting the following property, the problem gets simpler:

0.TALKTALKTALK... = TALK/9999 (try it with a 4 digit number, if you want to see it in action: http://lmgtfy.com/?q=1234/9999)

Thus, the equation turns into EVE/DID = TALK/9999 and then to EVE*9999 = DID*TALK.

Now it is easy to write this as a constraint model. If we choose to model in Essence Prime, use Tailor[1] to generate a Minion[2] input file from it, and then use Minion to actually solve the problem, it is solved almost instantaneously. Thanks to these two great tools!

The model I used is the following:

ESSENCE' 1.0
    find E : int(1..9)
    find V : int(0..9)
    find D : int(1..9)
    find I : int(0..9)
    find T : int(0..9)
    find A : int(0..9)
    find L : int(0..9)
    find K : int(0..9)
such that
    (E*100 + V*10 + E*1) * 9999 = (D*100 + I*10 + D*1) * (T*1000 + A*100 + L*10 + K*1),   
    alldiff([E,V,D,I,T,A,L,K])

If you have tailor and minion installed, just run the following commands to solve the problem.

java -jar tailor.jar -aux-info -out evedidtalk.minion evedidtalk.eprime

minion evedidtalk.minion -findallsols

It only takes less than 1 sec (both commands together) to find all two possible solutions.

[1] http://www.cs.st-andrews.ac.uk/~andrea/tailor
[2] http://sourceforge.net/projects/minion

Started using twitter feed

I've just started using twitter feed.

It is supposed to automatically tweet using my blog post's title in the associated twitter account.

I had already connected my twitter account to my facebook status.
So from now on, when I write a blog post, there will be an automatically generated tweet for the post, and a facebook status update.

Guess what? Facebook offers an application to update your twitter as well! What if I set both? Do they check for "circular automated updating"? Does such a thing exist?

Look all the power I have. I can push the entire internet in an infinite loop!

Collatz conjecture

Collatz sequence, if nothing else, is an interesting thing.

The clever German mathematician, Collatz, all of a sudden thought that any positive integer number, would create a sequence ending with 1 (or alternatively entering the 4-2-1-4 loop) when the following partial function is applied to it.

collatzSequence x
    | x <= 1 = [1]
    | even x = x : collatzSequence (div x 2)
    | odd  x = x : collatzSequence (3*x+1)

[ This is valid Haskell code by the way ]


And Collatz was right, most probably. That's not for sure since no proof for it exists, but using quite a lot of computing power a counter-example couldn't be found. So the question of whether Collatz was right or not stands as an open problem.


I, humbly, did some experiments and tried to have an idea looking at the lengths of such sequences. In addition to the analysis of lengths I had also tried to plot the sequences and investigate where sequences for consequent numbers catch up.
It was at least 3 (or 4?) years ago. And now that I present a more scientific profile, I thought I might come up with some more clever points. Initial results are *NOT* promising, but I'll keep on thinking.

Switching languages

[This is a rather unorganised chattering about programming languages and related thoughts.]

Being a devoted user of Microsoft technologies for some time, I am experiencing hard times switching to the real world again.

I was very much used to using C# for everything. I've been using it from the days of framework version 1.1 (now the version is 4.0). Actually I should make my point clearer, as a person suitable for the left-top part of this graphic, I've been using many technologies in parallel. Let's list the programming languages I used in the past 5 years:

C, C++, PHP, Javascript, Java, C#, Perl, Ruby (On Rails), Haskell. (tried to keep it chronologically ordered)


They all have pros and cons, compared to others. But I must admit; I loved programming in C back in the day, I never really liked programming in Java (although I had considerable amount of work done with it), and I enjoyed programming in C# very much.

As I said they all have some advantages over the others. For example Haskell is wonderful for some tasks, that you cannot deny using it. On the other hand Ruby with the wonderful On Rails framework was by far the best choice for our Senior project's web based information system.

I am pretty sure I can use the languages listed above (and possibly some others) effectively. But the one I feel myself comfortable with is C#. There are many reasons for this; such as it being a relatively newly designed language and consequently having a nicer design, the wonderful IDE support of VS, and many more.

I am now doing some programming for my PhD studies, and I am about to choose a language and a respective environment, given the constraint that I am using a MacBook now. It is too bad that my native (programming) language, C#, cannot be compiled to native code. (OK I know there are some options, but they are all hacks and tweaks)