Archive

Archive for the ‘Haskell’ Category

Primality test in Haskell

14 March 2012 Leave a comment

Problem: Implement a primality test in Haskell. Below is the code. The first implementation of the function divides uses a homemade function for finding the remainder when an integer is divided by another integer.

-- The remainder when a is divided by b.                                        
remainder :: Integer -> Integer -> Integer
remainder a b | a < b = a
              | a == b = 0
              | otherwise = remainder (a - b) b

-- Whether d divides n.                                                         
divides :: Integer -> Integer -> Bool                                        
divides d n = remainder n d == 0

The second implementation of divides uses the built-in function rem to find the remainder upon division by an integer.

-- Whether d divides n.  A more efficient version that uses the built-in        
-- function rem.                                                                
divides :: Integer -> Integer -> Bool
divides d n = rem n d == 0

The full primality test follows:

-- Whether d divides n.  A more efficient version that uses the built-in        
-- function rem.                                                                
divides :: Integer -> Integer -> Bool
divides d n = rem n d == 0

-- The least divisor of n that is at least k.                                   
ldf :: Integer -> Integer -> Integer
ldf k n | divides k n = k
        | k^2 > n = n
        | otherwise = ldf (k + 1) n

-- The least divisor of n.                                                      
ld :: Integer -> Integer
ld n = ldf 2 n

-- Primality test.                                                              
prime :: Integer -> Bool
prime n | n < 1 = error "must be a positive integer"
        | n == 1 = False
        | otherwise = ld n == n
Advertisements

Haskell snippet

5 November 2011 Leave a comment

Just some snippet of Haskell code today to return the last but one element of a list. The first implementation uses the built-in functions last and take.

-- Return the last but one element of a list.  This implementation uses         
-- last and take.                                                               
penlast :: [a] -> a
penlast xs = if null xs || length xs <= 2
             then head xs
             else last (take ((length xs) - 1) xs)

The second implementation below uses the built-in functions head and drop.

-- Return the penultimate element of a list.  This implementation uses          
-- head and drop.                                                               
penhead :: [a] -> a
penhead xs = if null xs || length xs <= 2
             then head xs
             else head (drop ((length xs) - 2) xs)
Categories: Haskell, programming Tags: ,

Haskell mode spews junk on first load

9 September 2010 Leave a comment

I’m using Haskell mode version 2.8.0 with Emacs 23.1.1 under Ubuntu 10.04.1 LTS. After loading a Haskell file, I would get the following garbage:

#[nil "\300C\207"
      [t]
      2]

Here’s what it looks like:

Acting on a tip from the ArchLinux community, I grep’d through all the Emacs Lisp files in the source distribution of Haskell mode 2.8.0 and found that the garbage in question is output by the following function in haskell-mode.el:

(eval-when-compile
  ;; Emacs 21 defines `values' as a (run-time) alias for list.                  
  ;; Don't maerge this with the pervious clause.                                
  (if (string-match "values"
                    (pp (byte-compile (lambda () (values t)))))
      (defsubst values (&amp;rest values)
        values)))

The culprit is the line

(pp (byte-compile (lambda () (values t)))))

I commented out that whole function and the junk is no longer seen when I first load a Haskell file.