Archive for July, 2009

Haskell, Eight Queens puzzle


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


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 triadflat—treeelse. Sometimes it is possible to elaborate it to 1-level — 2-levels — multilevel — more-dimensions.
Let’s look at several 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.


  • 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.


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.