Assignment 12 - Paradigm Functional: Haskell

---

Individual, Due: 2025 Aug 26, 11:59pm

IMPORTANT NOTE

---

Overview

---

The purpose of this assignment is to write Haskell functions to generate Moessner Miracle numbers. We will take advantage of the lazy evaluation feature of Haskell to generate and work with infinite lists.

This assignment is based on the video The Moessner Miracle. Why Wasn't this discovered for over 2000 years? by Mathologer.

The Moessner Miracle method can generate number sequences of various running sums, powers, or factorials, all without using multiplication. For example, we can use this method to generate all the positive squares (i.e., \(1^2=1\), \(2^2=4\), \(3^2=9\), \(4^2=16\), \(5^2=25\), ...).

We will use a combination of simple functions to generate number sequences. The first sequence of numbers are all the positive squares (\(1^2=1\), \(2^2=4\), \(3^2=9\), \(4^2=16\), ...), positive cubes (\(1^3=1\), \(2^3=8\), \(3^3=27\), \(4^3=64\), ...), and so on. The second sequence of numbers are factorials of positive integers (\(1!=1\), \(2!=2\), \(3!=6\), \(4!=24\), ...).

The simple functions used will operate on infinite lists to perform these operations:

• filter out ("highlight" in the Mathologer video) certain patterns of numbers, and
• compute a running sum ("Moessner sum" in video) of numbers.

Be sure to watch The Moessner Miracle. Why Wasn't this discovered for over 2000 years? by Mathologer.

IMPORTANT NOTE

---

Yes, I've said this already. It is important enough to mention it at least twice.

Requirements

---

Write the following Haskell functions. Full descriptions follow below along with examples at the bottom of the Requirements section.

skip_every_n :: Int -> [Int] -> [Int]	filter out every \(n\)th element of a list
skip_growing :: [Int] -> [Int]	filter out elements between growing runs
running_sum :: [Int] -> [Int]	compute running sums
moessner_powers :: Int -> [Int]	compute powers sequence
moessner_factorials :: [Int]	compute factorial sequence

For each of the functions above, you must demonstrate that your implementation is working correctly. To do this, include sample code and screenshots in your readme.html.

skip_every_n :: Int -> [Int] -> [Int] will filter out every \(n\)th element (first argument) in the given list. Note: the first element is included in the output! Only elements at indices that are multiples of the given Int are filtered out (starting indices at 1). See Mathologer video starting at 2:27.

skip_growing :: [Int] -> [Int] will filter out elements like skip_every_n, but with growing number of included elements. Here is a simple way to understand this function: include zero items, then skip one, then include one item, then skip one, include two items, skip one, include three items, skip one, include four items, skip one, and so on. Note: the first element is not included in the output! See Mathologer video starting at 9:59.

running_sum :: [Int] -> [Int] will compute the running sum of the given list. The first element is included; then the first and second elements are summed together; then the first, second, and third elements are summed; then the first through fourth elements are summed; and so on. IMPORTANT: for the \(n\)th output, you do not need to recompute the sum of first element to the \((n-1)\)th element, because that result was the \((n-1)\)th output you just previously computed! See Mathologer video starting at 2:38.

moessner_powers :: Int -> [Int] will produce a sequence of powers, \(i^n\) for a given \(n\), such as squares or cubes. See Mathologer video starting at 2:24.

moessner_factorials :: [Int] will produce a sequence of factorials, \(i!\). See Mathologer video starting at 9:54.

To get full points for...

• your implementations for skip_every_n, skip_growing, and running_sum must work with finite and infinite lists (demonstrate in readme)
• your implementations for skip_every_n, skip_growing, and running_sum must run in time linear to length of list (so far). In other words, computing the next element should be done in constant time.
• moessner_powers and moessner_factorials, your implementations must follow the methods outlined in the Mathologer video and produce infinite lists.

Example Outputs

Below is a table showing some example outputs for the functions you must implement. The first row is used as example input for skip_every_n, skip_growing, and running_sum. Note: your implementations should work with infinite lists to receive full credit!

list = [1..10]	:	1	2	3	4	5	6	7	8	9	10
skip_every_n 2 list	:	1	(skip)	3	(skip)	5	(skip)	7	(skip)	9	(skip)
skip_every_n 3 list	:	1	2	(skip)	4	5	(skip)	7	8	(skip)	10
skip_growing list	:	(skip)	2	(skip)	4	5	(skip)	7	8	9	(skip)
running_sum list	:	1	3	6	10	15	21	28	36	45	55
moessner_powers 2	:	1	4	9	16	25	36	49	64	81	100	...
moessner_powers 3	:	1	8	27	64	125	216	343	512	729	1,000	...
moessner_factorials	:	1	2	6	24	120	720	5,040	40,320	362,880	3,628,800	...

The (skip) table entries are there to give a visual indication of the values from list argument that are skipped over in the output.

Integer Overflow

The Int type in haskell is a fixed-width machine-specific integer with a minimum guaranteed range of \(-2^{29}\) to \(-2^{29}-1\). This is sufficient to computer up to \(20!\), but \(21!\) will cause an overflow, producing a negative result. Switching from Int types to Integer will prevent this, as the Integer type has arbitrary-precision.

IMPORTANT NOTE

---

Extra Credit

---

If you choose to implement these extra credit problems, be prepared to answer any question I may have about your implementation. I may call upon you to justify, clarify, or explain to me what you did. Again, these solutions must be developed, written, debugged by you. Do not use any other resource.

Also, you are responsible for testing your implementations and proving to me that you have tested your implementations. Be certain to test you implementations sufficiently against edge cases! Show your tests in your readme.html.

Implement the following functions (full descriptions below).

mergesort :: [Int] -> [Int]	sorts list using merge sort algorithm
quicksort :: [Int] -> [Int]	sorts list using quicksort algorithm
infix2rpn :: String -> String	converts expression from infix to reverse polish notation
evalrpn :: String -> Int	evaluates expression given in reverse polish notation

Write a mergesort :: [Int] -> [Int] function that sorts the input list of integers using merge sort technique. Much like the Sieve problem above, you will use multiple functions to solve this problem. Note: Merge sort runs in \(O(n \log n)\) time, therefore your implementation should also run in \(O(n \log n)\) to receive credit.

Write a quicksort :: [Int] -> [Int] function that sorts the input list of integers using quicksort technique. Note: Quicksort run in \(O(n \log n)\) time (assuming a good pivot is chosen), therefore your implementations should also run in the same time to receive credit.

Write an infix2rpn :: String -> String function that converts an expression (first parameter) from infix to reverse polish notation. For example, infix2rpn "3 + 4 * 5" will result in "3 4 5 * +". You can assume a valid infix expression consisting of only numbers and the + or * operators with spaces between. Tip: use the words :: String -> [String] function to convert the input parameter to a list of strings by splitting on spaces, and use the unwords :: [String] -> String function to convert a list of strings into a single string (with spaces between the "words").

Extend the infix2rpn function to accept parentheses for additional extra credit. For example, infix2rpn "( 3 + 4 ) * 5" returns 3 4 + 5 *.

Write an evalrpn :: String -> Int function that evaluates an expression in reverse polish notation. For example, evalrpn "3 4 5 * +" evaluates to 23. After using the words function on the input, you will need to use the read :: Read a => String -> a function to convert a String to an Int. For example, read "42" :: Int returns 42, while read "42" :: Float returns 42.0. The :: Int or :: Float determine which type (a in function definition) to convert the string into. Another example, let c a = (read a :: Int) in map c ["3","41","5"] returns [3,41,5].

If you have implemented the last three extra credit problems, calling evalrpn (infix2rpn "( 3 + 4 ) * 5") should return 35.

Feel free to add the following convenience function to your Haskell file. I wrote this function to be understandable, not necessarily efficient.

-- Similar to words function, but handles missing/extra spaces
-- between ops, digits, parens.  Note: not general or robust!
mywords :: String -> [String]
mywords s = parser [] s
    where
        isparen c = (c == '(' || c == ')')
        isop    c = (c == '+' || c == '*')
        isdigit c = (c >= '0' && c <= '9')
        -- readint reads digits until non-digit
        -- returns ("digit","remainder of string")
        readint "" = ("","")
        readint (h:t)
            | (isdigit h) = (h:(fst (readint t)), snd (readint t))
            | otherwise  = ("", h:t)
        parser l "" = l
        parser l (h:t)
            | (isdigit h) = parser (l ++ [fst (readint (h:t))])
                                   (snd (readint (h:t)))
            | (isop h)    = parser (l ++ [h:""]) t
            | (isparen h) = parser (l ++ [h:""]) t
            | h == ' '    = parser l t

Using mywords instead of words allows you to specify the infix expression without needing to separate out each entity (digit, op, parenthesis) with spaces. For example:

evalrpn (infix2rpn " (3+  4) *5 ")

IMPORTANT NOTE

---

Resources

---

Several free versions of Haskell are available. See the Notes.

Grade Template

---

	Implementation
3pts	Correct skip_every_n function
3pts	Correct skip_growing function
3pts	Correct running_sum function
3pts	Correct moessner_powers function
3pts	Correct moessner_factorials function
	Submission
3pts	Submitted Haskell source (.hs)
3pts	Include testing code in readme.html as codeblock
3pts	readme.html with screenshots
	Extra Credit
+3pts	Correct mergesort implementation
+3pts	Correct quicksort implementation
+3pts	Correct infix2rpn implementation
+3pts	Extend infix2rpn to handle parentheses
+3pts	Correct evalrpn implementation

Getting Help

---

This is an individual assignment. If you have questions about your general solution or about your particular implementation (e.g., your code), ask the prof or TA!

need help with	ask
understanding the problem	professor, TA, or peer
developing a solution	professor or TA
implementing and debugging	professor or TA

Do NOT use any other resource for help, hints, etc. Your submission should be your own work, and your work alone!

Submit

---

Submit via course LMS a Zip file containing the Haskell source, readme.html, and evidence of your code working (screen snapshot).

If you did the extra credit, include screenshots in the readme.html.