Haskell: Sieve of Eratosthenes

Recently I needed to compute prime numbers starting from 2 and on to x , Sieve of Eratosthenes seemed like a simple and straightforward (albeit not too fast) way to get this done


eliminator :: Int -> [Int] -> [Int]
eliminator _ [] = []
eliminator start list = filter (\x -> x `rem` start /= 0) list

sieve :: [Int] -> [Int]
sieve [] = []
sieve (x:xs) = x : (sieve $ eliminator x xs)

*Main> sieve [2..100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

There is one known limitation -- sieve assumes that the first number in the sequence is a prime.

CRC32

Another piece fell into place

calc_adler32 :: String->Int->Int->Int

calc_adler32 [] a b = (b `shiftL` 16) .|. a

calc_adler32 str a b  = 

  let ap = (a + (ord $ head str)) `mod` mod_adler

      bp = (ap + b) `mod` mod_adler

  in calc_adler32 (tail str) ap bp

    

crc32 :: String -> Int

crc32 str = calc_adler32 str 1 0

*Main> crc32 "abc"
38600999

Set permutations

There is a part of my project that calls for a permuted set, that is given the original set of elements create a set of sets where each set contains a permutation of the original.  It turns out that this is more or less simple once you break the problem down into smaller parts.

There are a few algorithms to generate permutations,  I chose interleaving for it being relatively simple and straight forward.
For a set of [x,y, x] permute the first two elements
[[x, y], [y, x]]
and then interleave each set with z
[[z, x, y], [x, z, y], [x, y, z], [z, y, x], [y, z, x], [y, x, z]]

First we create a function that would take a list an a value and create permutations of that list with a value:

interleaveSet :: [a] -> a -> [[a]]
interleaveSet [] value = [[value]]
interleaveSet xs value = [ take pos xs ++ [value] ++ drop pos xs | pos <- [0..length(xs)] ]

Here are some samples:

*Main> interleaveSet [] 1
[[1]]
*Main> interleaveSet [1] 2
[[2,1],[1,2]]
*Main> interleaveSet [1,2,3,4] 5
[[5,1,2,3,4],[1,5,2,3,4],[1,2,5,3,4],[1,2,3,5,4],[1,2,3,4,5]]

So we now have a way of interleaving a set with a value, but remember that what we need to do is build this from an existing set.  What we need is something that will take the output of interleaveSet and interleave the sets created by it with the next value.  I was at first tempted to use a list comprehension once again

interleaveSets sets value = [ interleaveSet set value | set <- sets ]

but since interleaveSet outputs a [[a]] and interleaveSets will create a list of those, our return value will be [[[a]]], which is not what we want at all.


*Main> interleaveSets (interleaveSet [1,2,3,4] 5) 6
[[[6,5,1,2,3,4],[5,6,1,2,3,4],[5,1,6,2,3,4],[5,1,2,6,3,4],[5,1,2,3,6,4],[5,1,2,3,4,6]],[[6,1,5,2,3,4],[1,6,5,2,3,4],[1,5,6,2,3,4],[1,5,2,6,3,4],[1,5,2,3,6,4],[1,5,2,3,4,6]],[[6,1,2,5,3,4],[1,6,2,5,3,4],[1,2,6,5,3,4],[1,2,5,6,3,4],[1,2,5,3,6,4],[1,2,5,3,4,6]],[[6,1,2,3,5,4],[1,6,2,3,5,4],[1,2,6,3,5,4],[1,2,3,6,5,4],[1,2,3,5,6,4],[1,2,3,5,4,6]],[[6,1,2,3,4,5],[1,6,2,3,4,5],[1,2,6,3,4,5],[1,2,3,6,4,5],[1,2,3,4,6,5],[1,2,3,4,5,6]]]

Since we want to be able to feed it back to interleaveSets, this is not what we want.

This will do:

interleaveSets :: [[a]] -> a -> [[a]]
interleaveSets [] value = [[]]
interleaveSets (s:sets) value = interleaveSet s value ++ interleaveSets sets value

*Main> interleaveSets (interleaveSet [1,2,3,4] 5) 6
[[6,5,1,2,3,4],[5,6,1,2,3,4],[5,1,6,2,3,4],[5,1,2,6,3,4],[5,1,2,3,6,4],[5,1,2,3,4,6],[6,1,5,2,3,4],[1,6,5,2,3,4],[1,5,6,2,3,4],[1,5,2,6,3,4],[1,5,2,3,6,4],[1,5,2,3,4,6],[6,1,2,5,3,4],[1,6,2,5,3,4],[1,2,6,5,3,4],[1,2,5,6,3,4],[1,2,5,3,6,4],[1,2,5,3,4,6],[6,1,2,3,5,4],[1,6,2,3,5,4],[1,2,6,3,5,4],[1,2,3,6,5,4],[1,2,3,5,6,4],[1,2,3,5,4,6],[6,1,2,3,4,5],[1,6,2,3,4,5],[1,2,6,3,4,5],[1,2,3,6,4,5],[1,2,3,4,6,5],[1,2,3,4,5,6],[]]

I am not sure what that empty element at the end is, will have to deal with it later (I am sure it is a side effect of my base case)

Ah the solution is that the base case return a [] because any set ++ [] is just set

*Main> [1,2,3] ++ []
[1,2,3]

And here is the new result:
*Main>  interleaveSets (interleaveSet [1,2,3,4] 5) 6
[[6,5,1,2,3,4],[5,6,1,2,3,4],[5,1,6,2,3,4],[5,1,2,6,3,4],[5,1,2,3,6,4],[5,1,2,3,4,6],[6,1,5,2,3,4],[1,6,5,2,3,4],[1,5,6,2,3,4],[1,5,2,6,3,4],[1,5,2,3,6,4],[1,5,2,3,4,6],[6,1,2,5,3,4],[1,6,2,5,3,4],[1,2,6,5,3,4],[1,2,5,6,3,4],[1,2,5,3,6,4],[1,2,5,3,4,6],[6,1,2,3,5,4],[1,6,2,3,5,4],[1,2,6,3,5,4],[1,2,3,6,5,4],[1,2,3,5,6,4],[1,2,3,5,4,6],[6,1,2,3,4,5],[1,6,2,3,4,5],[1,2,6,3,4,5],[1,2,3,6,4,5],[1,2,3,4,6,5],[1,2,3,4,5,6]]

And finally to put it all together:

permuteSet :: [a] -> [[a]]
permuteSet [] = []
permuteSet set = foldl(\acc e -> interleaveSets acc e) seed (tail set)
  where seed = interleaveSet [] (head set)

Lets test

*Main > permuteSet [1,2,3,4]
[[4,3,2,1],[3,4,2,1],[3,2,4,1],[3,2,1,4],[4,2,3,1],[2,4,3,1],[2,3,4,1],[2,3,1,4],[4,2,1,3],[2,4,1,3],[2,1,4,3],[2,1,3,4],[4,3,1,2],[3,4,1,2],[3,1,4,2],[3,1,2,4],[4,1,3,2],[1,4,3,2],[1,3,4,2],[1,3,2,4],[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]

Looks about right

*Main> length $ permuteSet [1,2,3,4]

24

Number of permutations is equal to n! / (n -k)!

Where k is the number of elements from n per permutation, in our case k = n so that turns into 0! which we know is one

and the factorial of 4 is 4 * 3 * 2 *1 = 24

A more readable haskell string tokenizer

Another crack and a tokenizer

otherTok :: String -> [Char] -> [[Char]]
otherTok [] _ = []
otherTok cs delim = foldl(\acc c -> if c `elem` delim then [] : acc else (head acc ++ [c]) : (tail acc) ) [] cs

*Main> otherTok "blah,blah blah. blah! blah" " ,.!"
["blah","","blah","","blah","blah","*** Exception: Prelude.head: empty list

Encountering a delimiter char produces an empty string, which I can remove later with filter, not sure what to do with the Exception.

P.S. Problem solved

otherTok :: String -> [Char] -> [[Char]]
otherTok [] _ = []
otherTok cs delim = foldl(\acc c -> if c `elem` delim then [] : acc else (head acc ++ [c]) : (tail acc) ) [""] cs

*Main> filter (/="") (otherTok "blah,blah blah. blah! blah" " ,.!")
["blah","blah","blah","blah","blah"] 

P.S.S The tokens that result are in reverse order of how the words show up in a line, also easily fixed 

rev :: [a] -> [a]
rev [] = []
rev xs = foldr(\x acc -> acc ++ [x]) [] xs 
 *Main> rev(filter(/="") (otherTok "abc,def.ghi" ",."))
["abc","def","ghi"] 

Or just use the builotin reverse and stop trying to reinvent the wheel

haskell string tokenizer

I recently needed a function to split strings on a delimeter and found this one on http://blog.julipedia.org/2006/08/split-function-in-haskell.html:


tokenizeString :: String -> [Char] -> [[Char]]
tokenizeString [] _ = [""]
tokenizeString (c:cs) delim
  | c `elem` delim = [] : rest
  | otherwise = (c : head rest) : tail rest
    where rest = tokenizeString cs delim

It took me a little while to wrap my mind around the recursion and what goes on here, a pen and some paper and trace it out this is really really cool.   It's a shame that I was not able to come up with this on my  own.

Execution trace original string: "a,b" delimiter list: ","

I shortened some names to save space by hMt is really head $ mT and tmT is tail $ mT where mT is myTokenizer.  I am no expert, but the secret sauce appears to be in the base case which always returns a [""] -- list of strings.  And how the string elements are concatenated:

Char : [Char]: [[Char]]  -- Single character to a string to a list of strings