Hannah (eightyoldwomen) wrote,
Hannah
eightyoldwomen

booshka

what I've been up doing for part of the night:
*Actually I'm going to rewrite some of it tomorrow so that's it's a little more coherent verbally. Embedded in the mess is some of my 3:00 humor, but the important thing is that it works.

-- Math 121 Lab 3 - Using Haskell to implement languages and automata
--
-- Math 121 Lab
-- date : 10/01/07
--

--Problem 3
--The function, "konKat," concatenates two lists of integers that represent the strings of a language(s). (I know the problem asked to use lists of lists to represent strings, but you said it was ok to do it this way.) The concatenation function only works for strings over the alphabet of natural numbers, excluding 0. The output of "konKat" provides the list of strings resulting from concatenation, removing any duplicates that occur by means of a helper function "removeDuplicates," which was developed in Lab 2. The actually computation of the concatenation is aided by two other helper functions digitsOfpos and power, which were created for Lab 1. Their role is explained in more detail below.


digitsOfpos :: Int -> Int
digitsOfpos n | n >= 10 = 1 + (digitsOfpos (n `div` 10))
| n < 10 = 1
| otherwise = 0

power :: Int -> Int -> Int
power x n | n == 0 = 1
| n > 0 = x * (power x (n - 1))
| otherwise = 0
-- - - - - - - - - -
--The following four functions, created for Lab 2, remove duplicates in a list and put them in ascending order.

sort :: [Int] -> [Int]
sort [] = []
sort [x] = [x]
sort (h:t) = (sort lessers) ++ [h] ++ (sort greaters)
where lessers = t `filteredBy` ( <= h )
greaters = t `filteredBy` ( > h )

[] `filteredBy` pie = []
(h:t) `filteredBy` pie = if (pie h) then (h:t') else (t')
where t' = filter pie t


remover [] _ f = f
remover (h:t) [] f = remover t [h] (h:f)
remover (h:t) (x:d) f
| h /= x = remover t (h:(x:d)) (h:f)
| h == x = remover t (h:(x:d)) f

removeDuplicates [] = reverse (remover [] [] [])
removeDuplicates (h:t) = reverse (remover (sort(h:t)) [] [])

-- - - - - - - - - - -
--Pit is a somewhat unnecessary function, employed merely for aesthetic purposes, as the author wanted to clear up the amount of functions in the "kon" function. Pit raises 10 to the power of the number of digits in an integer, x.

pit :: Int -> Int
pit x = power 10 (digitsOfpos x)

--"kon" does most of the concatenation computation. It multiplies the head of the first list ten raised to the power of the number of digits of the head of the second list and adds the head of the second list to that value.(whew!, e.g. if [2,3,4,5] and [23,4,3,4] are concatenated, then it computes 2*10^(2) + 23 = 223, which is the concatenation of the first two strings.) The function then repeats this process for the head of the first list and each element of the second list, creating a list of the head of the first list concatenated with the second list.

kon :: [Int] -> [Int] -> [Int]
kon (h : t) [] = (h : t)
kon [] (x:d) = (x:d)
kon (h : t) (x : d) | (h:t) /= [] = (h * (pit x) + x) : (kon (t) (x : d))
| otherwise = []

--konKat applies the kon function to the rest of the first list, providing the full concatenation of both lists. It also employs "removeDuplicates" to provide a more ordered list.

konKat (h : t) [] = (h : t)
konKat [] (x:d) = (x:d)
konKat (h : t) (x : d) = removeDuplicates ((kon (h : t) (x : d)) ++ (konKat (h : t) (d)))
  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic
  • 2 comments