Archive

Archive for the ‘Haskell’ Category

Primality test in Haskell

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

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
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
else head (drop ((length xs) - 2) xs)
Categories: Haskell, programming Tags: ,

Haskell mode spews junk on first load

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.

Categories: documentation, Emacs, Haskell, Linux