Tuesday, November 14, 2006

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.

89 Comments:

Anonymous Anonymous said...

Hi Brian

Your Stack datatype is essential equal to the normal [] (List) datatype, except that you have ruled out the possibility of an empty stack.

But why don't you just use the following implementation of stacks:

empty = []

push stack elem = elem : stack

pop (elem : stack) = stack

top (elem : stack) = elem

All operations are cheap constant time operations.

2:06 AM  
Blogger a said...

Thanks for the info, ken. :)

11:12 AM  
Blogger Tony Morris said...

O(2n) is equivalent to O(n). The function runs in time linearly proportional to the size of the list (n)

;)

4:38 PM  
Anonymous Anonymous said...

[B]NZBsRus.com[/B]
Skip Crawling Downloads Using NZB Downloads You Can Quickly Find HD Movies, Games, Music, Applications & Download Them @ Dashing Speeds

[URL=http://www.nzbsrus.com][B]Usenet[/B][/URL]

3:41 PM  
Anonymous Anonymous said...

[B]NZBsRus.com[/B]
Lose Slow Downloads With NZB Files You Can Instantly Find High Quality Movies, Console Games, MP3 Albums, Software and Download Them @ Dashing Rates

[URL=http://www.nzbsrus.com][B]Usenet[/B][/URL]

4:06 PM  
Anonymous Anonymous said...

Hit to the zoological with two backs casinos? pass over this youthful [url=http://www.realcazinoz.com]casino[/url] advisor and safe conduct up online casino games like slots, blackjack, roulette, baccarat and more at www.realcazinoz.com .
you can also discontinuation our fresh [url=http://freecasinogames2010.webs.com]casino[/url] by at http://freecasinogames2010.webs.com and flourish in trustworthy folding shin-plasters !
another remote [url=http://www.ttittancasino.com]casino spiele[/url] stance is www.ttittancasino.com , because german gamblers, array not involved online casino bonus.

10:29 PM  
Anonymous Anonymous said...

Someone deleted several links from letitbit and shared servers.

From now, we will use www.tinyurlalternative.com as our default [url=http://www.tinyurlalternative.com]url shortener[/url], so every url will be there and visible for everyone.

You can pick out from many great [url=http://kfc.ms]short url[/url] address like:

kfc.ms easysharelink.info jumpme.info megauploadlink.info megavideolink.info mygamelink.info myrapidsharelink.info mytorrentlink.info myurlshortener.com mywarezlink.info urlredirect.info urlshrinker.info weblinkshortener.com youtubelink.info and many others.

They maintain above 60 other available domains and the [url=http://myurlshortener.com]url shortener[/url] service work properly for free without any registration needed.

So we assume it is good notion and suggest you to use [url=http://urlredirect.info]url redirect[/url] service too!

Thank you.

6:10 AM  
Anonymous Anonymous said...

It isn't hard at all to start making money online in the hush-hush world of [URL=http://www.www.blackhatmoneymaker.com]blackhat blog[/URL], You are far from alone if you haven’t heard of it before. Blackhat marketing uses not-so-popular or little-understood methods to produce an income online.

6:27 PM  
Anonymous Anonymous said...

About casinos? wrench this advanced [url=http://www.realcazinoz.com]casino[/url] counsel and shtick evasively online casino games like slots, blackjack, roulette, baccarat and more at www.realcazinoz.com .
you can also disappoint our up to the two shakes of a lamb's tail log [url=http://freecasinogames2010.webs.com]casino[/url] orientate at http://freecasinogames2010.webs.com and pick up chief lolly !
another voguish [url=http://www.ttittancasino.com]casino spiele[/url] change situation is www.ttittancasino.com , during german gamblers, visit unrestrained online casino bonus.

3:54 AM  
Anonymous Anonymous said...

[B]NZBsRus.com[/B]
Replace Idle Downloads Change To NZB Files You Can Quickly Find High Quality Movies, Console Games, MP3s, Applications and Download Them at Maxed Out Speeds

[URL=http://www.nzbsrus.com][B]Binaries Usenet[/B][/URL]

8:22 AM  
Anonymous Anonymous said...

Greetings im new to this forum i hope i will be able to help and contribute here because iv learned allot myself.

Cheers

[URL=http://plasteringcoursesuk.co.uk][B]plastering courses essex[/B][/URL]

5:40 AM  
Anonymous Anonymous said...

SMARTS - that's the name of today's online income affiliate game. You already have "smarts?" Good, that gives you a head start. Yet, the catch is, knowing exactly when, how, where, and what strategies to implement with the God-given smarts you possess. Many a well-intended online income affiliate has landed on the side-shores of this vast Internet sea
click here

3:40 AM  
Blogger sandrabullock said...

Make $3000-$40000 A Month by Using internet At Home, Internet is quickly growing into a world-wide marketplace, which provides a unique opportunity for everyday people like you and me to cash in on it and start making money online! make $400 per day

12:01 AM  
Anonymous adult sex teen stories said...

Bill stared hard at the freshly fucked beaver, then dropped to his knees andstared right into it with his hands framing the spread. Thanks Taking the cake box he turned to leave when he felt asmall hand on his back.
underage animal sex stories
bdsm branding stories
super young teen sex stories
hot porn stories
bdsm bull whipping stories
Bill stared hard at the freshly fucked beaver, then dropped to his knees andstared right into it with his hands framing the spread. Thanks Taking the cake box he turned to leave when he felt asmall hand on his back.

3:17 AM  
Anonymous Anonymous said...

how to unlock iphone 4
unlock iphone 4
unlock iphone 4

http://www.gpucomputing.net/node/6013?q=node/1280 http://www.columbusneighborhoods.org/content/summer-fun-events-columbus?page=1
It was awhile ago when I saw it, but there is apparently something you can download and burn to a disk and it will delete just about everything from your computer to make reformatting easier. Anybody know what the website is? There are missing, necessary files on our desktop or there may have been a virus and now its all screwy. I just got a laptop so was able to transfer all the stuff I needed from the desktop to the laptop, so it'd be better just to reformat since I already have everything backed up here so to speak.
iphone 4 unlock unlock iphone 4

unlock iphone 4 [url=http://unlockiphone44.com]how to unlock iphone 4[/url] how to unlock iphone 4 unlock iphone 4

5:49 AM  
Anonymous Anonymous said...

top [url=http://sweden-online-casino.com/]free casino[/url] coincide the latest [url=http://www.realcazinoz.com/]casino bonus[/url] manumitted no consign hand-out at the leading [url=http://www.baywatchcasino.com/]casino compensation
[/url].

6:04 PM  
Anonymous Anonymous said...

[url=http://www.23planet.com]online casino[/url], also known as accepted casinos or Internet casinos, are online versions of acknowledged ("buddy and mortar") casinos. Online casinos definite someone assume gamblers to lessen and wager on casino games completely the Internet.
Online casinos normally invite odds and payback percentages that are comparable to land-based casinos. Some online casinos navigate higher payback percentages in the servicing of bias gismo games, and some tumble upon known payout proportion audits on their websites. Assuming that the online casino is using an fittingly programmed apathetic youngster up generator, recount games like blackjack comprise an established prohibit edge. The payout stretch commission of these games are established at closest the rules of the game.
Countless online casinos explode out or holdings their software from companies like Microgaming, Realtime Gaming, Playtech, Worldwide Imposture Technology and CryptoLogic Inc.

7:51 AM  
Anonymous Anonymous said...

[url=http://onlinecasinose25.com ]internet casino [/url]avec une physionomie de sagesse et de contentement tout à fait http://sverigeonlinecasino.net/ online casino malta internet casino det løftede Lys, mens hun aabnede sin Dør og lukkede den bag dem.

10:39 AM  
Anonymous Anonymous said...

larousse easy cooking ebook http://audiobookscollection.co.uk/Programming-Role-Playing-Games-with-DirectX/p153984/ free ebook downloands [url=http://audiobookscollection.co.uk/es/Thinking-Nursing/p222800/]the mystery method ebook[/url] free dsc-f828 ebook

1:55 AM  
Anonymous Anonymous said...

xanax online xanax dosage for anxiety attacks - generic xanax pill identifier 029

11:30 AM  
Anonymous Anonymous said...

generic xanax xanax for generalized anxiety disorder gad reviews - xanax pills g3719

3:13 PM  
Anonymous Anonymous said...

buy tramadol online buy generic tramadol online - tramadol hcl 50 mg efectos secundarios

6:06 PM  
Anonymous Anonymous said...

buy tramadol online tramadol dose get high - can you buy tramadol online legally

6:48 PM  
Anonymous Anonymous said...

generic xanax xanax withdrawal opiates - buy xanax online cheap

5:29 AM  
Anonymous Anonymous said...

buy tramadol online 5 50 mg tramadol - tramadol side effects 50mg

10:47 AM  
Anonymous Anonymous said...

xanax online long 2mg xanax kick - xanax dosage white pill

8:12 AM  
Anonymous Anonymous said...

tramadol without prescription buy cheap tramadol mastercard - tramadol for getting high

1:25 PM  
Anonymous Anonymous said...

buy tramadol online methocarbamol and tramadol for dogs - tramadol dosage canine weight

3:31 AM  
Anonymous Anonymous said...

generic xanax generic xanax footballs - alprazolam cinfa 0 5 mg

7:37 AM  
Anonymous Anonymous said...

buy carisoprodol carisoprodol soma scheduled drug - listaflex carisoprodol 350 mg para que sirve

8:09 AM  
Anonymous Anonymous said...

buy tramadol online tramadol dosage effects - tramadol hcl extended release

11:56 AM  
Anonymous Anonymous said...

buy tramadol online get tramadol online - tramadol medication addiction

3:53 AM  
Anonymous Anonymous said...

xanax online xanax bars in system - xanax dosage for sleep aid

4:01 PM  
Anonymous Anonymous said...

buy tramadol online buy tramadol line usa - tramadol hcl nih

8:10 PM  
Anonymous Anonymous said...

generic xanax xanax on a drug test how long - xanax recreational dose

8:32 AM  
Anonymous Anonymous said...

carisoprodol 350 mg much carisoprodol soma - carisoprodol with codeine

3:23 PM  
Anonymous Anonymous said...

carisoprodol 350 mg carisoprodol how long does it stay in your system - carisoprodol half life

5:39 PM  
Anonymous Anonymous said...

Hello. Facebook takes a [url=http://www.onlinecasinos.gd]casinos[/url] wager back on 888 casino sell: Facebook is expanding its efforts to present real-money gaming to millions of British users after announcing a practise with the online gambling companions 888 Holdings.And Bye.

3:06 AM  
Anonymous Anonymous said...

tramadol online pharmacy tramadol for dogs forum - cheap tramadol with no prescription

8:08 AM  
Anonymous Anonymous said...

buy tramadol online tramadol withdrawal codeine - tramadol 200mg

8:53 AM  
Anonymous Anonymous said...

buy tramadol online tramadol 50mg buzz - tramadol 100mg sr side effects

4:04 PM  
Anonymous Anonymous said...

buy tramadol online tramadol hcl 25 mg - buy tramadol online usa

4:49 PM  
Anonymous Anonymous said...

buy xanax online no prescription cheap buy xanax online usa - xanax side effects in elderly

3:25 AM  
Anonymous Anonymous said...

buy tramadol online best place to buy tramadol online reviews - order tramadol cod

9:00 AM  
Anonymous Anonymous said...

buy tramadol online tramadol online no rx - high dosage of tramadol

9:47 AM  
Anonymous Anonymous said...

buy cialis online cialis daily for sale - cialis dosage

2:01 AM  
Anonymous Anonymous said...

cialis online no prescription overnight cialis online au - buy generic cialis online us

4:47 AM  
Anonymous Anonymous said...

buy cialis online cialis daily risks - buy cialis online germany

9:56 AM  
Anonymous Anonymous said...

generic xanax xanax bars online cheap - generic xanax 2mg pills

1:22 PM  
Anonymous Anonymous said...

cialis pills cialis 2.5 price - cheap cialis prices

10:43 PM  
Anonymous Anonymous said...

cialis online generic cialis date - safe order cialis online

4:51 AM  
Anonymous Anonymous said...

cialis online http://www.cialis-online-shop - cialis daily how long does it take to work

12:27 PM  
Anonymous Anonymous said...

http://landvoicelearning.com/#62431 gabapentin tramadol withdrawal - tramadol 50 mg generic ultram

1:44 AM  
Anonymous Anonymous said...

buy tramadol tramadol hcl + kidney - tramadol hcl generic name

1:46 AM  
Anonymous Anonymous said...

20000 :) Cheap Gabapentin - neurontin online no prescription http://www.neurontinonlinecheap.net/#Cheap-Gabapentin, [url=http://www.neurontinonlinecheap.net/#Neurontin-Online]Neurontin Online[/url]

4:27 PM  
Anonymous Anonymous said...

http://landvoicelearning.com/#23561 buy tramadol no prescription cod - best site purchase tramadol

5:57 PM  
Anonymous Anonymous said...

buy tramadol tramadol withdrawal hell - buy tramadol cheap no prescription

4:17 AM  
Anonymous Anonymous said...

buy tramadol with mastercard tramadol 93 58 pill - buy tramadol online no prescription cheap

6:18 AM  
Anonymous Anonymous said...

buy tramadol 100mg tramadol 50 mg compared to vicodin - can you buy tramadol online in usa

2:11 AM  
Anonymous Anonymous said...

buy tramadol tramadol jwh 018 - tramadol for dogs anti inflammatory

4:08 AM  
Anonymous Anonymous said...

http://landvoicelearning.com/#21906 tramadol 20mg - is tramadol/ultram an opiate

7:50 AM  
Anonymous Anonymous said...

buy tramadol overnight tramadol no prescription cod - ultram side effects weight loss

7:52 AM  
Anonymous Anonymous said...

buy tramadol buy generic tramadol - buy tramadol online no prescription usa

11:22 PM  
Anonymous Anonymous said...

buy tramadol buy tramadol cod overnight delivery - cheaptramadolonline

7:14 AM  
Anonymous Anonymous said...

buy tramadol no prescription overnight tramadol withdrawal vertigo - best way buy tramadol online

6:45 PM  
Anonymous Anonymous said...

http://blog.dawn.com/dblog/buy/#34852 tramadol hcl usa - tramadol zyrtec interaction

9:10 PM  
Anonymous Anonymous said...

http://reidmoody.com/#37982 ativan quick acting - lorazepam 1 mg bijwerkingen

3:22 PM  
Anonymous Anonymous said...

buy ativan online buy ativan online canada - ativan yeast infections

5:35 PM  
Anonymous Anonymous said...

buy ativan online buy lorazepam 0.5 mg - ativan side effects memory

11:02 AM  
Anonymous Anonymous said...

http://reidmoody.com/#92465 buy lorazepam online india - ativan sublingual online

5:41 AM  
Anonymous Anonymous said...

How can I find cheap, reliable wordpress web-site designers that I can out source
my webdesign work to?

Feel free to visit my web page ... http://paginasamarillas-atl.com

9:22 AM  
Anonymous Anonymous said...

http://staam.org/#92453 tramadol japan - tramadol injection

11:50 PM  
Anonymous Anonymous said...

A huge dick in my pussy,the warm wet tounge up our arse and cum and also
pussy juice all over me. Fuck, ozzy

my website - hcg injections
my web site: hcg injections

3:49 PM  
Anonymous Anonymous said...

http://staam.org/#21236 buy tramadol online new zealand - tramadol 50mg yahoo

9:37 PM  
Anonymous Anonymous said...

http://ranchodelastortugas.com/#61301 xanax bars bad you - xanax overdose complications

6:07 PM  
Anonymous Anonymous said...

http://ranchodelastortugas.com/#71453 xanax bars order - xanax generic brand name

7:25 PM  
Anonymous Anonymous said...

Hi, buy modafinil - buy provigil online no prescription http://www.provigilpills4sale.com/, [url=http://www.provigilpills4sale.com/]buy modafinil online [/url]

6:15 AM  
Anonymous Anonymous said...

Li, cheap prozac - order prozac http://www.prozacorder365.net/, [url=http://www.prozacorder365.net/]fluoxetine online[/url]

5:13 AM  
Anonymous Anonymous said...

xanax generic xanax overdose seizures - xanax for mri anxiety

9:08 AM  
Anonymous Anonymous said...

http://ranchodelastortugas.com/#37284 long you high xanax - explain xanax high

2:24 AM  
Anonymous Anonymous said...

cheap generic xanax extended release xanax dosage - xanax on drug screen test

7:31 PM  
Anonymous Anonymous said...

2, [url=http://www.klonopincheaponline.com/]Klonopin's Effect On Anxiety[/url] - Klonopin's Effect On Anxiety - buy klonopin no prescription http://www.klonopincheaponline.com/ .

1:01 PM  
Anonymous Anonymous said...

12, [url=http://www.klonopinforsaleonline.com/]buy clonazepam without prescription [/url] - order clonazepam - buy cheap clonazepam online http://www.klonopinforsaleonline.com/.

3:18 PM  
Anonymous Anonymous said...

12, [url=http://www.acomplia20mgonline.com/]acomplia no prescription [/url] - generic rimonabant - where can i buy acomplia online http://www.acomplia20mgonline.com/.

3:23 PM  
Anonymous Anonymous said...

Yοur oωn write-up offers verifieԁ beneficial to us.
It’s very useful and you're clearly really experienced in this region. You have exposed my face in order to various views on this topic with intriquing, notable and strong written content.

my web page viagra online
Take a look at my weblog ; viagra online

5:48 PM  
Anonymous Anonymous said...

Pelvic surgery may include surgery to remove an appendix or ovarian cysts. Getting pregnant all starts with both parties as a couple, and never really with one party's desire to get pregnant. The sensation of pregnancy makes a mother feel in high spirits.
http://pregnancyhelper.in

5:41 PM  
Anonymous Anonymous said...

I'm amazed, I have to admit. Seldom do I come across a blog that's equally educativе and amusing, аnd without а doubt,
you've hit the nail on the head. The issue is something too few people are speaking intelligently about. I am very happy that I came across this in my search for something regarding this.

My blog; weight loss meal plan

9:17 AM  
Anonymous Anonymous said...

Striking pctures
http://matures.net.erolove.in/?jaida
free adult entertainment erotic navel erotic pregnancy top erotic books adult movies

2:57 PM  
Blogger Unknown said...

5-health.com/health-tips/benefits-lychee-real-food-life

1:46 AM  

Post a Comment

<< Home