More Haskell and Some Nemerle

16 04 2007

Ive recently had to complete a paper so I have not been able to do too much programming. However, even in the few days that I have used it Haskell has allowed me to write extremely short yet expressive programs, whose equivalence I would not know how to write so simply in C++ or C#. The programs are pretty simple. In one, I have a function which takes a list of numbers and a function and builds a modulo table using the function which I have defined prior.

Basically it makes a modulo table for Zn = [0.. (n-1)].

aMod :: Int -> Int -> Int -> Int

aMod a b m = (a + b) `mod` m
mMod a b m = (a * b) `mod` m

modulo_table a f =
	let k = length a in
	[((f i 1 k), (f 1 j k), (f (f i 1 k) (f 1 j k) k) )  | i <- a, j <- a]

I know the above is not efficient since it applies f at least twice more than it needs to. If anyone knows how it can be improved please tell. However it was done as such to make it easier to check from the Hugs output thing. In a real program I’d simply make a list [f i j k | i <- a, j <- a ] and format it accordingly. But I havent gotten to monads yet :)

modulo_table2 [0..3] aMod
[0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2]

modulo_table [0..11] mMod
[(0,0,0),(0,1,0),(0,2,0),(0,3,0),(0,4,0),(0,5,0),(0,6,0),(0,7,0),(0,8,0),(0,9,0),(0,10,0),(0,11,0),(1,0,0),(1,1,1),(1,2,2),(1,3,3),(1,4,4),(1,5,5),(1,6,6),(1,7,7),(1,8,8),
(1,9,9),(1,10,10),(1,11,11),(2,0,0),(2,1,2),(2,2,4),(2,3,6),(2,4,8),(2,5,10),(2,6,0),(2,7,2),(2,8,4),(2,9,6),(2,10,8),(2,11,10),(3,0,0),(3,1,3),(3,2,6),(3,3,9),(3,4,0),
(3,5,3),(3,6,6),(3,7,9),(3,8,0),(3,9,3),(3,10,6),(3,11,9),(4,0,0),(4,1,4),(4,2,8),(4,3,0),(4,4,4),(4,5,8),(4,6,0),(4,7,4),(4,8,8),(4,9,0),(4,10,4),(4,11,8),(5,0,0),(5,1,5),
(5,2,10),(5,3,3),(5,4,8),(5,5,1),(5,6,6),(5,7,11),(5,8,4),(5,9,9),(5,10,2),(5,11,7),(6,0,0),(6,1,6),(6,2,0),(6,3,6),(6,4,0),(6,5,6),(6,6,0),(6,7,6),(6,8,0),(6,9,6),(6,10,0),
(6,11,6),(7,0,0),(7,1,7),(7,2,2),(7,3,9),(7,4,4),(7,5,11),(7,6,6),(7,7,1),(7,8,8),(7,9,3),(7,10,10),(7,11,5),(8,0,0),(8,1,8),(8,2,4),(8,3,0),(8,4,8),(8,5,4),(8,6,0),(8,7,8),
(8,8,4),(8,9,0),(8,10,8),(8,11,4),(9,0,0),(9,1,9),(9,2,6),(9,3,3),(9,4,0),(9,5,9),(9,6,6),(9,7,3),(9,8,0),(9,9,9),(9,10,6),(9,11,3),(10,0,0),(10,1,10),(10,2,8),(10,3,6),
(10,4,4),(10,5,2),(10,6,0),(10,7,10),(10,8,8),(10,9,6),(10,10,4),(10,11,2),(11,0,0),(11,1,11),(11,2,10),(11,3,9),(11,4,8),(11,5,7),(11,6,6),(11,7,5),(11,8,4),
(11,9,3),(11,10,2),(11,11,1)]

——————-
The next program I wrote is one which allows one to compose permutation groups and can build cayley tables for said permutation groups. I do not see it being difficult to extend to be more general but then Cayley’s Theorem would have that doing that may not even be necessary. hehe. Basically it takes a map described as a tuple (which is basically what a function is in the mathematical sense) and follows the the pairs to create a composition.

{-The task of the algorithim is to go through each tuple in the list and for each tuple try to match the given variable.
The matched tuples opposite pair is returned and matched to some iteration -}

sec list2 a = head [b | (n,b) <- list2, n == a]

o :: [(Int,Int)] -> [(Int,Int)]-> [(Int,Int)]
o list1 list2 = let n = length list1 in [ (a, (sec list1 (sec list2 a)) ) | a <- [1..n]]

//////////////

Hugs> a
[(1,2),(2,3),(3,1)]
Hugs> a `o` e `o` r `o` b
(1,3),(2,2),(3,1)]

This example works on the symmetry group of a triangle.

e,a,b,r,s,t::[(Int,Int)]

l = [(e,'e'),
(a,'a'),
(b,'b'),
(r,'r'),
(s,'s'),
(t,'t')]

e = [(1,1),(2,2),(3,3)]
a = [(1,2),(2,3),(3,1)]
b = [(1,3),(2,1),(3,2)]

r = [(1,1),(2,3),(3,2)]
s = [(1,3),(2,2),(3,1)]
t = [(1,2),(2,1),(3,3)]

(&) j k  = [ b | (n,b) <- l, n == (j `o` k)]

cayley_table = [  ( b, d, a&c    )  | (a,b) <- l, (c,d) <- l]

cayley_table
[('e','e',"e"),('e','a',"a"),('e','b',"b"),('e','r',"r"),('e','s',"s"),('e','t',"t"),
('a','e',"a"),('a','a',"b"),('a','b',"e"),('a','r',"t"),('a','s',"r"),('a','t',"s"),
('b','e',"b"),('b','a',"e"),('b','b',"a"),('b','r',"s"),('b','s',"t"),('b','t',"r"),
('r','e',"r"),('r','a',"s"),('r','b',"t"),('r','r',"e"),('r','s',"a"),('r','t',"b"),
('s','e',"s"),('s','a',"t"),('s','b',"r"),('s','r',"b"),('s','s',"e"),('s','t',"a"),
('t','e',"t"),('t','a',"r"),('t','b',"s"),('t','r',"a"),('t','s',"b"),('t','t',"e")]

The cayley table is based around assigning pairing a letter to a group element. Then the operator (&) basically matches the element of a predefined list to the composition of the given elements.

#pragma indent
using System;
using System.Console;
using Nemerle.Utility;
using Nemerle.Collections;

module Program

aMod (a :int, b : int, m : int) : int
	(a + b) % m

mMod (a:int, b:int, m : int) : int
	(a * b) % m

modulo_table2 (a : list[int], f : (int * int* int)-> int)  : list[int]
	def k = List.Length(a)
	$[f(i, j , k)  | i in a, j in a]

//this feels me with unhappiness. if anyone knows how pattern matching on tuples works in nemerle please let me know.
sec(list2 : list[(int * int)], a : int): int
	def tup = List.Head(List.Filter(list2, fun(x) { if(x[0]==a)true else false}  ) )//  Head $[v[1] | v in list2, v[0] == a]
	tup[1]

public static @<.> (list1 : list[(int * int)], list2 : list[(int * int)]) : list[(int * int)]
	def n = List.Length(list1);
	$[ ( /**/ a, sec(list1, sec(list2, a) ) /**/) | a in [1..n]]

Main() : void

	def m = Int32.Parse(ReadLine()) - 1
	def z = modulo_table2($[0..m], aMod)

	def e = [(1,1),(2,2),(3,3)]
	def a = [(1,2),(2,3),(3,1)]
	def b = [(1,3),(2,1),(3,2)]

	def r = [(1,1),(2,3),(3,2)]
	def s = [(1,3),(2,2),(3,1)]
	def t = [(1,2),(2,1),(3,3)]

	def l = [(e,'e'),(a,'a'),(b,'b'),(r,'r'),(s,'s'),(t,'t')]

	mutable n = 0;
	def chk (j , k)
	$[ x[1] | x in l, x[0] == j <.> k]

	def cayley_table = $[  ( b, d, chk(a,c)   )  | (a,b) in l, (c,d) in l]

	mutable n = 0;

	foreach(a in z)
		Write($"$a ")
		if(n < m) n++
		else
			n=0
			WriteLine("")

ReadLine()

12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11 0
2 3 4 5 6 7 8 9 10 11 0 1
3 4 5 6 7 8 9 10 11 0 1 2
4 5 6 7 8 9 10 11 0 1 2 3
5 6 7 8 9 10 11 0 1 2 3 4
6 7 8 9 10 11 0 1 2 3 4 5
7 8 9 10 11 0 1 2 3 4 5 6
8 9 10 11 0 1 2 3 4 5 6 7
9 10 11 0 1 2 3 4 5 6 7 8
10 11 0 1 2 3 4 5 6 7 8 9
11 0 1 2 3 4 5 6 7 8 9 10




Haskell

12 04 2007

I have been trying to write programs in OCaml, with the keyword here being trying. What little I managed to learn has faded quite quickly due to my disuse of the knowledge. So far I have been programming by “instinct”:

randoms snips:

let addm a b m = (a + b) mod m
let mm a b m = (a * b) mod m

let eq a b m = let g = a - b in if (g mod m) == 0 then true else false;;

let f n = let rec g a b n l = if n + 1 == List.length l then l else g (a + b) a n ( a ::l) in g 0 1 n []

let rec general_sorder_reccurence b a p q n l = if n + 1 == List.length l then l else general_sorder_reccurence (p*a + q*b) a p q n (a::l)

let sqf n = List.map (fun x -> x * x) (f n)
let sumf n = List.fold_left (+) 0 (sqf n)

let fgen_l n = let rec gen_l n l = if List.length l == n then l else gen_l n ((sumf (List.length l)) :: l) in gen_l n []

Coding by ear is no fun so I decided I need to read a book on functional programming as I do not really have time to learn by experimentation. So I picked up a book on Functional programming taught with Haskell.

So far I must say I quite like this language and do not find it esoteric at all (perhaps it is because I never got too steeped in imperative programming or because I meet with the cousins of many of the notions of the language daily). Although I feel the Ocaml syntax (especially its pattern matching stuff) can be quite elegant, Haskell is alot more natural.

List comprehension and lazy evaluation are also really useful tools. (Nemerle has both of these too). I have only just begun and shall be reporting in with more substantial learnings as time passes.





Hiatus

8 04 2007

I have been busy trying to get into a comfortable schedule with life and so had to go on a forced blogging hiatus. I am now back on path and should be able to blog regularly henceforth.