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
Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: