Posts Tagged ‘Haskell’




Let N = any number not divisible by 2 and 5.
Does there exist a k (for each such N), such that 10^k – 1 is divisible by N?
Or: Is there 99..9 for any N, such as 99..9 is divisible by N, if N is coprime with 10?


Yes.  It is multiplicative order of 10 modulo N. The sequence is can be found at The On-Line Encyclopedia of Integer Sequences.




-- all numbers than cannot be devided by 2 or 5
seq1 :: [Integer]
seq1 = filter (\a->(a `mod` 10) `elem` [1,3,7,9]) [1..]

-- find 99..9 that can be devided by n
findNum n = head $ [x | x<-[1..], (10^x-1) `mod` n == 0]

--prints the sequene
take 100 $ map findNum3 seq2


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]

three star programmer


There is a nice set of articles on, three star XXX;

It started  from *** in C – as it states, “Being called a ThreeStarProgrammer is usually not a compliment”.

There is a similar concept in PerlThreeStarPerl (I don’t speak Perl enough to understand this…) and  ThreeStarJava (three layers of inner classes).

Probably similar  “rating” can be invented for more languages. For Lisp it could be something like “number of sequential closing brackets” (probably it is only notable when more than ten; just to remind, that nobody knows what whether it stands for Lost in Stupid Parentheses or Language of Insufferable Superfluous Parentheses).

I think I can be rated as 3-star Haskeller as I wrote a sequence of three map.

h15 = 1 : foldl1 merge ( ap (map map (map (*) [2, 3, 5])) [h15])

I believe it is readable; probably it is bad.

Programming languages should die


There are too many programming languages, and almost all of them must die.
There is no reasons (other then historic) for most of them.

The only exceptions:
C++ (upcoming version) – when you need uncompromising performance. Kind of multiplatform multiparadigm assembler.
Python – pseudocode, when you want only a proof of concept or when speed isn’t important, or for education.
Haskell – when you want to enjoy the process of writing code.

Although Paul Graham says LISP is the only computer programming language so far to be discovered, rather than invented, it is wrong. With all the respect to Lisp/Scheme and their elegance, those cannot be not quick enough (beeing dynamic-typed) nor pure enough (like Haskell), so they must die.

Here is a “proof” that Haskell is not “invented” but “discovered” – Curry-Howard isomorphism – it is just a notation of mathematical concept.

So is also SQL and Prolog, but those those, of course, should die, too.
SQL probably can be replaced by library (e.g. Haskell), LINQ, Google’s MapReduce. Everything done in Prolog is can be quite easy done on any functional language, but not vice-versa. It is good only for very specific tasks, and I don’t believe in domain-specific languages.

Undoubtfully, C#, Java and Delphi/(Object) Pascal, D etc. must die – there is no real reason for them to exist – they are too close to C++, but with many compromises.

Lua is similar to but worse than Python – and  thus must be replaced by it.

(Visual) Basic, Fortran and Cobol should never been born at all:  It’s well known that teaching Basic is a crime, and that the inventor of Fortran regrets about it.

Algol, Pl/2, Modula, Ada etc.  were important once, are obsolete.

So  are C with classes, Objective-C, Smalltalk and even Eiffel, with all the respect.

Perl is write-only language. It is not necessary. “Yes, sometimes Perl looks like line noise to the uninitiated, but to the seasoned Perl programmer, it looks like checksummed line noise with a mission in life.” Awk, Bash-scripts etc. – all can be easily replaced by, say,  Python. They can be implemented as a library, no need for separate language.

There is no reason to use ML, OCaml, F# – if you want to write functional-style – use Haskell, otherwise – don’t pretend (or use Python or use Boost).

I  can continue: Forth is write-only, assemblers aren’t portable (use C++), PHP is inconsistent etc.

JavaScript/ActionScript (EcmaScript) ? Nice language.  But die anyway!

Hamming numbers


Hamming aka Ugly, 5-smooth aka Regular numbers.
It is considered to be a trivial task to write it using any functional language, but very difficult on imperatice languages.
My goal is to check whether it is easy (possible) to write a lazy algorithm on functional-style on C++ using boost library (generator_iterator or proto library).

Before I start with c++, let me play with Haskell and Python to understand what I want.
Merge is boring on both languages.

--does WordPress supports Haskell syntax highlight? probably not...
merge xx@(x:xs) yy@(y:ys)
 | x  y = y : xx `merge` ys
 | otherwise = x : xs `merge` ys
def merge(it1, it2):
        if (i1i2):
                yield i2
                yield i1

def merge3(l1, l2, l3):
    merge(l1, ( i for i in merge(merl2, l3)))
  • Python version 1:Now, Python.
    Interesting discussion can be found here, but I changed it to work on Python 3K and too look nicer. (For me, almost always shorter == nicer.

    def m1_235():
     yield 1
     for i in merge3((2*i for i in m1_235(),
     3*i for i in m1_235(),
     5*i for i in m1_235()):
     yield i
  • Python version 2:It uses internal tool to be more lazy: it frees unneeded memory. Haskell (as beeng more lazy) does this automatically.
    from itertools import tee
    def m3_235():
         def _m235():
             yield 1
             for n in merge3((2*i for i in m2),
                         (3*i for i in m3),
                         (5*i for i in m5)):
                 yield n
         m1 = _m235()
         m2, m3, m5, mRes = tee(m1, 4)
         return mRes
    it = m3_235()

    Now, let’s have fun with haskell

  • Taken from WikiPedia
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
  • more one-line variants
h2= 1 : map (2*) h2 `merge` map (3*) h2 `merge` map (5*) h2
h3= 1 : foldl1 merge [map (2*) h3, map (3*) h3, map (5*) h3]
h7= 1 : foldl1 merge [map ((*) 2) h7, map((*) 3) h7, map((*) 5)h7]
h11 = 1 : foldl1 merge (map ((flip $ x->;map $(x*)) h11) [2, 3, 5])
h12 = 1 : foldl1 merge [map f h12 |f <- map (*) [2, 3, 5]]
h15 = 1 : foldl1 merge ( ap (map map (map (*) [2, 3, 5])) [h15])
h16 = 1 : foldl1 merge [ [f h | h<-h16 ] | f <- map (*) [2, 3, 5]]
h17 = 1 : foldl1 merge [ [f h | h<-h17, f<-[(*2), (*3), (*5)]]]
h18 = 1 : foldl1 merge [ [f h | h<-h18, f<-map (*) [2, 3, 5]]]
h19 f1 f2 f3= (1 : foldl1 merge ( ap (f1 f2 (f3 (*) [2, 3, 5])) [h19 f1 f2 f3]))-- take 111 (h19 map map map)
h20 = 1 : foldl1 merge ( ap (f f (f (*) [2, 3, 5])) [h20]) where f=map

to test them, you should write something like take 111 h2

To be continued: Probably with prolog and C++