Haskell Stacks : Two Different Ways

I am starting to attempt to understand how Haskell can persist functions sans the variables. You can do it with lists, already. There are plenty of functions that demonstrate the concept. But I want to expand further. I want to try implementing a stack with a list, and then do it with a recursive type. This is what I have for the first one:

putAtEnd [] item = [item]
putAtEnd (x:xs) item = x : putAtEnd xs item

push lst item = putAtEnd lst item
-- or
-- push lst item = reverse (item : (reverse lst))

pop lst = pop_ lst ((length lst) - 1)

pop_ _ 0 = []
pop_ (x:xs) len = x : pop_ xs (len - 1)

-- or
-- pop lst = reverse (tail (reverse lst))

I thought the reverse function was neat, but seemingly costly. But, from the Prelude:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

flip f x y = f y x

foldl f z [] = z
foldl f z (x : xs) = foldl f (f z x) xs

We can see a really slick way of doing reverses. "reverse" is merely a function curry of a foldl waiting for the last parameter. Let's see if it is costly:

reverse [1,2,3,4]
 -> foldl (flip (:)) [] [1,2,3,4]
    -> foldl (flip (:)) (flip [] 1) [2,3,4]
    -> foldl (flip (:)) (1 : []) [2,3,4]
          -> foldl (flip (:)) (flip [1] 2) [3,4]
          -> foldl (flip (:)) (2 : [1]) [3,4]
                -> foldl (flip (:)) (flip [2,1] 3) [4]
                -> foldl (flip (:)) (3 : [2,1]) [4]
                      -> foldl (flip (:)) (flip 4 : [3,2,1]) []
                      -> foldl (flip (:)) [4,3,2,1] []
-> [4,3,2,1]

So, the ones with the same indentation are the same, except the second line is the flip function evaluated. It is what I expected, though. It takes O(n) (?) time (there are two operations on the data: one operation to flip, and another operation to add to the new list. So, maybe it is O(2n)? I forget my algorithm lessons.) It seems though, that the original implementation I provided performs the same though. Maybe expressing it via reverse then is easier.

Lists are, still probably still efficiently implemented, and those operations I am doing are turned into an iteration (tail-call recursion), plus some other magic I don't know about. I have to think of a nifty way of handling it faster though.

Anyway, the other idea I had was to make a stack a recursive data type:

data Stack n m = Item m | StackFrame ((Stack n) (Item m))

-- so ... 

(StackFrame (StackFrame (Item 1) (Item 2)) (Item 3))

-- looks like

-- 3
-----
-- 2
-----
-- 1
-----

What a wacky idea. I have to think about this one, and read some common examples on this.

Haskell Golf Scores

I am tutoring someone in Java. We did an example program of summing up the golf scores of a number of people. I was interested in showing him some MVC design principles, as it will be useful for his end-of-year project.

I decided to improve my understanding of Haskell today, by reimplementing it in Haskell. It lacks MVCishness, but it's still nice. I also couldn't find a function to convert from strings to integers, so I implemented one quickly using a number->int function. It is not perfect, since it does conversions to hex digits, but it is a start.

Can I improve on it? Please do comment. ;)

module GolfScore where

import Data.Char

toNumber str =
 let slen = length str
 in
   toNum_ str ((length str) - 1) 0

toNum_ :: [Char] -> Int -> Int -> Int
toNum_ str (-1) val = val

toNum_ str count val =
 let currVal = (str !! count)
 in toNum_ str (count - 1)
        (val + ((digitToInt currVal) * (10 ^ (((length str) - 1) - count))))

----------
-- main
----------
run count holes = run_ count holes [] []

run_ 0 holes lstName lstRes = showResults (reverse lstName) (reverse lstRes)
run_ count holes lstName lstRes =
   do putStr "Enter name: "
      n <- getLine
      scores <- getAndAddScores holes []
     
      run_ (count -1) holes (n : lstName)
               ((foldr ((+) . toNumber) 0 scores) : lstRes)


showResults [] _ = return ()
showResults (x:xs) (y : ys) =
   do
     putStr x
     putStr " got a score of: "
     print y
     showResults xs ys   


getAndAddScores 0 scores = do return scores
getAndAddScores holes scores =
   do
      putStr "Enter score: "
      score <- getLine
      getAndAddScores (holes - 1) (score : scores)

This Weblog

I am going to post random samples of code that look interesting to me in languages I am trying out. Right now, I have to look at other programming languages that I do not completely know. It will start off with a lot of Haskell and Ada code.