CS-460-1.Fall-2005:Homeworks:JeffBaileyHomework
From CSWiki
Contents |
[edit] Homework 1
Comments / Notes / Questions:
- Find IDE that is NOT emacs based.
- Nested if (not elseif)?
[edit] Median
- Definately inefficient due to duplicate calls to Length and Sort
- Bugs: doesnt handle infinite or nil list nicely
% returns median value from list.
% If no true median exists, returns list containing two surrounding values
declare fun {Median L}
if {IsList L} then
if {IsEven {Length L}} then
[{Nth {Sort L Value. '<'} ({Length L} div 2)} {Nth {Sort L Value. '>'} ({Length L} div 2)}]
else
{Nth {Sort L Value. '<'} ({Length L} div 2 + 1)}
end
end
end
local L1 L2 L3 in
L1 = [22]
L2 = ['Charlie' 'Alpha' 'Echo' 'Delta' 'Bravo']
L3 = [4 2 1 3 5 6]
{Browse [{Median L1} {Median L2} {Median L3}]}
end
[edit] Count
- Improvements: eliminate trivial recursions
- Bugs: Infinite lists?
% computes the number of atomic elements in a nested list.
declare fun {ElementCount List}
case List of Head|Tail then
if {IsList Head} then
% head is list? recurse
{ElementCount Head} + {ElementCount Tail}
else
% head atomic? count it!
1 + {ElementCount Tail}
end
else
% nil? dont count
0
end
end
local L1 L2 L3 L4 in
L1 = [10]
L2 = [20 21 22 23]
L3 = [30 L1 L2 31]
L4 = [40 L1 L2 L3 41]
{Browse [L1 {ElementCount L1}]}
{Browse [L2 {ElementCount L2}]}
{Browse [L3 {ElementCount L3}]}
{Browse [L4 {ElementCount L4}]}
end
[edit] Tree
- Completely useless experimentation
- AVL tree?
% simple tree experimentation, nothing special
declare proc {Insert Key Value TreeIn ?TreeOut}
if TreeIn == nil then
TreeOut = tree(Key Value nil nil)
else
local tree(K1 V1 T1 T2) = TreeIn in
if Key == K1 then
TreeOut = tree(Key Value T1 T2)
elseif Key < K1 then
local T in
TreeOut = tree(K1 V1 T T2)
{Insert Key Value T1 T}
end
else
local T in
TreeOut = tree(K1 V1 T1 T)
{Insert Key Value T2 T}
end
end
end
end
end
local T1 T2 T3 in
{Insert 10 'Ten' nil T1}
{Insert 5 'Five' T1 T2}
{Insert 20 'Twenty' T2 T3}
{Browse T3}
end
