Haskell, Eight Queens puzzle

Just a list of Google search result for Haskell solutions of  Eight Queens, annotated.

• Wikipedia - backtracking depth-first search, 11 lines including printing result
• literateprograms.org – 11 lines.
• c2 – two solutions 4 and 5 lines, using list  comprehension  or fold
• Haskell tutorial at Walla Walla University, wwc – 4 lines, list  comprehension
• magnus blog – N-Queens solution, relatively long, code translated from Standard ML, uses exceptions. There is another solution (in comments), 147bytes long
• Memorial University – long solution Monadic that uses State Transformer
• Aarhus university –  6 lines including printing, list comprehensions.
• paulbutler.org – “N-Queens in a Tweet” – 160 bytes, including printing
• haskell.org – a thread comparing performance vs C language
• wikibooks.org – 6 lines, use fold (same as C2 solution)
• harold – 7 lines, uses map.
• All About Monads – Monadic Solution
• UNSW; a journal of Haskell programming – 12 lines, nice solution.
• Sententia cdsmithus@wordpress.com – 10 lines, using writer monad
• RAMONHASKELL - translation of C program that generates  CNF clauses

eight queens

Eight queens puzzle, first attempt (will be updated later)

import Control.Monad

legalqueens :: [Int] -> Bool
legalqueens [] = True
legalqueens (s:sx) = not (or [not (legalqueens sx),
 s `elem` sx,
 s `elem` zipWith (-) sx [1..],
 s `elem` zipWith (+) sx [1..]
 ])
f1 = do
 a <- [1..8]
 b <- [1..8]
 c <- [1..8]
 d <- [1..8]
 e <- [1..8]
 f <- [1..8]
 g <- [1..8]
 h <- [1..8]
 guard $ legalqueens [a,b,c,d,e,f,g,h]
 return [a,b,c,d,e,f,g,h]

Fighting the trees, or looking for new dimentions; Computer science reviewed

The Triad

Trees are ubiquitous in computer science. Everything is tended to be represented as tree; many times it seems to be natural representation of everything, even when it is definitely not good enough. In certain areas we’ve overgrown, in certain areas we are still there.
Generally, any CS concepts can be seen as kind of dialectic triad – flat—tree—else. Sometimes it is possible to elaborate it to 1-level — 2-levels — multilevel — more-dimensions.
Let’s look at several examples.

Examples

Let’s look at several examples.

File system

• First file systems were flat. Thy are still used e. g.  in supercomputers and smartcards.
• Next requirement  was group files for certain criteria, e.g. by owner or by purpose. Thus folders (directories) and file extensions were invented.
• The obvious enhancement  of this idea is tree-like file system with recursive (sub)folders.
• Tree is definitely not good enough, and everybody knows it. Simplest example: say, I want to organize my MP3-library; I have “music” folder, containing “Russian”, “Hebrew”, “English” etc. subfolders, each containing,  folder with “Reggae” and “Heavy Metal”, followed by subdirectories  with artist names. Surely, this method (and any other) fails: what if I want look list of reggae songs regardless of the language? Where should I put artist who performs on more than one language or genre? What if I want to store his pictures near his songs? Hierarchical filesystems fails everyvere alll the time; possible improvements include symbolic links, tags and more.

Object-oriented

• In the beginning, there was the Primordial Spaghetti.  (Basic, first Cobols and Fortrans…)
• Modular programming (OO without inheritance) can be seen as “2-level” generalization. (CLU, Visual Basic…)
• Object-Oriented is the well-known development of this concept. Being better than the first two, it still sucks hard. It is just not good enough for real life. Famous Circle-Ellipse problem is only one of it’s countless  issues.
• Design Pattern’s trend arose as an attempt to solve OO troubles. Aspect Oriented is another attempt. Functional programming solves many troubles, but it has it’s own drawbacks.

Execution Flow

• In first computer programs, program execution either goes forward or (conditionally or unconditionally) jumps, like classic Turing Machine.
• Functions and procedures are more advanced; control flow forms a tree (I continently forget goto as it considered harmful).
• Goto (aka call-cc) and exceptions handling are certain advancement. Still more powerful and flexible approaches are needed for parallel programming.

Non-CS taxonomies fail, too.

Of course, similar problems occur not only in computer science.

For example, while botanic taxonomies are great, there are certain  properties that do not fit the tree; being a succulent and tree are examples of properties that “cross” the taxonomic tree. Botanic trees appear in different orders and families (different branches of taxonomic tree). Something similar to “tags” is used to describe plant.  Parallel evolutions and hybrids also complicate the “tree”.

Any military or corporative hierarchy fail to describe real structure of organization.  Many times society is more anarchistic than it seems.

Conclusion

Many things theta are represented as trees, should not. Sometimes general graphs suits better. Sometimes new, not-yet-invented paradigms are needed.

What is wrong with tabs in source code?

For some reason, almost all code conventions prohibit use of tab character (they recommend using spaces).
For example, in Real Word Haskell p. 66 and they state that tabs are bad and repeat in chapter 3: “[...] never use tab characters in Haskell source files. Use spaces.”
The explanation: tab character may look different for different users.
But why is it bad? I like using source code with tabs, because I can define tab as 2, 3, 4 or 8 spaces; I cannot do it with a source that uses spaces.
So, I see many reasons using tabs for tabulation instead of spaces (assuming you use it consistently):

Configurability: I define the size of tab, depending on my preferences, screen size or whatever. Dictating me the size of tab is no more logical than saying me what font color to use.

Ease of use: turn “cursor through tabs” oftion off; backspaces/delete button deletes tab; navigating code is easier

Consistancy: tab char enforces you to use equal identation

Revertability: converting tab to X spaces is easy; converting X spaces to tab is more difficult, when you don’t know X value.

stateless

Being pure functional programmer and anarchist, I hate the state and class hierarchies.

javascript & call/cc

Consider simple example:
function foo() performs a simple AJAX call bar() (web method in ASPX terminology), that returns a value.
Something like:

function foo()
{
   return pageMethods.bar();
}

The code above is wrong, of course. Ajax call is asynchronous; it does not return value immediately. Instead, it takes a callback function as a parameter:

function foo()
{
   calback=function(result)
   {
     alert(result);
     return result;
   }
   return pageMethods.bar(callback);
}

But we still have a problem, because foo returns immediately, and alert is called only later. foo returns nothing.
Call-with-current-continuation could solve this problem, but javascript doesn’t have it.
Of course, there is (more than one) way to solve this, but I don’t know any nice way to do it.

I’ve another blog that talks about continuations and javascript: http://marijn.haverbeke.nl/cps/

book

Today I got Real World Haskell book

geek plans

Things I would do if I had more time:

Haskell

• Learn Haskell better.
• Write seminar (non-deterministic monad tutorial) and get my degree.
• Submit some code to shoutout (The Computer Language Benchmarks Game) to prove everybody Haskell is coolest language
• Improve LambdaBot (pl modeule) using technique from here

Prolog

• finish course & write a project (probably poddavki or amazons).
• submit missing items to shootout

General, Libraries

• learn more about DesignPatterns
• learn more about Aspect-oriented programming
• learn more modules in Boost library
• learn Ogre, CEGUI – understand how good are they, also for my job.
• understand, how Tags, Tag cloud etc. can be more useful in life.

Open-Source

• continue with tng development.
• write a plugin for Firefox that uses Knuth’s mathematical spacing algorithm for text formatting.
• Tabs support for gvim.

games

• improve my chess
• improve my go skills
• write (javascript?) maxit

How to explain programming paradigmas to you girlfriend

Recipes are often used as to explain what algorithm is.

Let’s take a simplified vegan Chocolate Cake recipe as an example:

var
	175g self raising white flour
	3 level tsp baking powder
	25g cocoa
	100g Barbados sugar
	125 ml olive oil
	325 ml cold water
begin
	Preheat oven to 190°C.
	Place all the cake ingredients in a bowl
		and mix thoroughly.
	Place mixture in greased loaf tin
		and bake for 30 minutes
		in the preheated oven.
	Cool on a wire rack.
	Arrange the chocolate beans on top.
end.

Low-level (Assembly) start be something like:

	Find to oven
	Make sure it is empty
	turn temperature switch to "190°"
	...
	and so on

Procedural/Modular would be similar to original formulation.

Functional (my favorite) could be:

...place mixed cake ingredients
    in a bowl
     and put it to the pre-heated oven for 30 min...

Logic/Descriptive programming:

What you are trying to do is cake.
Cake is round and sweet and tasty.
(try everything until you get it)

Object-Oriented is somehow difficult to make straightforward here.

I’ve tried this analogy on my gf, and it worked.

The interesting part is that although most males (like me) find “low-level” recipes most easy to use, more experienced people (and cookbooks) prefer “functional” formulations (which does not implicitly state the “order of evaluation”), as it is shorter and and is easier for “optimizations“(*),  “thread synchronizations“(**) and “multiprocessors“(***) and so on – exactly the advantages of fp.

(*) by optimization I mean, that in “functional” formulation, it is easier to understand that e.g. which jobs can be swapped, omitted etc.

(**) example of synchronization: “put baked A and roasted cut B to C and mix” is easier to both understand and prepare than

put A on fire;
cut C; put C on fire.
repeat:
    If A is ready turn A off.
    If B is ready turn off B.
until both are ready;
mix them

(***) Multiprocessors: If you have, say, two cooks and an instruction “take baked A and roasted and cut B to and mix”, the tasks can be trivially assigned in optimal way, but is much harder in more low-level recipe.

Hamming Numbers in prolog

Basic testing weather a number is hamming is straightforward. It can be something like this:

hamming(X) :- X =< 0, !, fail.
hamming(1).
hamming(X) :-0 =:= (X mod 2), !, Y is X // 2,  hamming(Y).
hamming(X) :-0 =:= (X mod 3), !, Y is X // 3,  hamming(Y).
hamming(X) :-0 =:= (X mod 5), !, Y is X // 5,  hamming(Y).

But if want to make an ordered list of of all hamming numbers using lazy algorithm, we should try harder.

See this nice site that compares functional and logical languages for a solution.

His solution uses dif predicate to make the evaluation lazy. There are also other predicates for co-routines in Prolog, like freeze.

Prolog’s  freeze/frozen are similar to scheme’s promise/force.