In this blog post, I'll attempt to explain some basic concepts of Functional Programming, using Haskell. This blog post isn't about Haskell per-se, but about one way of approaching this problem, which demonstrates the benefits of functional programming.
You can run most of these examples in ghci, by saving the contents of the example into a .hs file, loading up ghci and running :load file.hs.
Many thanks to Mattox Beckman for coming up with the programming exercise, and Junjie Ying for coming finding a better data structure for this explanation than I came up with.
You are Hercules, about to fight the dreaded Hydra. The Hydra has 9 heads. When a head is chopped off, it spawns 8 more heads. When one of these 8 heads is cut off, each one spawns out 7 more heads. Chopping one of these spawns 6 more heads, and so on until the weakest head of the hydra will not spawn out any more heads.
Our job is to figure out how many chops Hercules needs to make in order to kill all heads of the Hydra. And no, it's not n!.
Prelude: Simple Overview Of Haskell Syntax
Before we dive into code, i'll explain a few constructs which are unique to Haskell, so it's easy for non Haskellers.
- List Creation: You can create a list / array using the : operator. This can even be done lazily to get an infinite list.
- Defining Function: Looks just like defining a variable, but it takes parameters. One way they are different from other languages is the ability to do pattern matching to simplify your code. Here, I define a method that sums all the elements of a list.
- More List Foo: Adding lists can be done with ++. Checking if a list is empty can be done with null. You can use replicate to create a list with the same elements over and over.
Choosing a data structure
Let's choose a simple data structure to represent the hydra. We'll pick an array to represent the heads of the Hydra, using the
level of each head as the value. The initial state of the Hydra (with 9
level 9 heads) can be represented as follows:
[9, 9, 9, 9, 9, 9, 9, 9, 9].
Chopping off a head
The whole point of functional programming is to build small functions and compose them later. We'll build a few functions, specific to our domain, and a few more general ones to orchestrate.
Let's first build a specific function to chop off the Hydra's head. We know that chopping off one
level 9 head should result in 8
level 8 heads (and 8 of the original
level 9 heads). This is represented as
[8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9]
Let's build the chop function. It takes a single argument, and the current levels of the all live heads. It will return the state of the heads after chopping the first one.
The three lines of code below map to these rules:
- If there are no heads left, just return
- If we find that there is a level 1 head at the start of our list, just chop it off and return the rest of the array
- If we find that there is a higher level head at the start of our list, spawn n - 1 heads in it's place
Repeatedly chopping heads
Our function chop is a pure function as, given some input, it always returns the same output, without any sort of side effects. Side effects is a general term for modifying inputs / IO Operations / DB Calls, and so on.
Since chop is pure function, we can safely call it over and over. Let's build a list where each element is the result of chopping the previous element.
This paradigm is so common, that we have a functional construct that does this: iterate. We can replace the above code with the following:
Truncate that infinite list
Great, we now have built a list of all the states the Hydra is in while Hercules is busy chopping away at it. However, this list goes on forever (we never put in a termination condition in the earlier code), so let's do that now.
We can use a simple empty check (null) to test if the hydra is still alive. Let's keep items as long as the Hydra is alive
Putting the two together
Again, these patterns are so common, that we can replace the entire thing with a single line. takeWhile keeps things in the list until the first element that doesn't match.
Now that we have the sequence of chops needed to kill that Hydra, figuring out the number of chops is just a matter of figuring out how long the sequence is.
Now that we've solved the problem, what next? How easy is it to extend this? Let's add a new requirement: Hercules, though a half god, can only fight at most n Hydra heads at a time. If the number of Hydra heads goes above n, then hercules dies. Let's make a function
willHerculesDie which takes two parameters, n and the Hydra.
Turns out, this is pretty simple. We just need to count all the heads that are alive. If the count is more than n at any point, then we return true, and Hercules dies.
So what next?
We've built a bunch of really composable functions, and we can look at each one independently to tune the system.
You can get Haskell set up with the Haskell Platform and play around with the code here.
Some great books you can check out:
- Structure and Interpretation of Computer Programs
- Learn you a Haskell for Great Good - Greatest Haskell Tutorial out there
- Functional Programming for the Object-Oriented Programmer
If you liked this post, you could:
I am glad that I saw this post. It is informative blog for us and we need this type of blog thanks for share this blog, Keep posting such instructional blogs and I am looking forward for your future posts. Python Projects for Students Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account. Project Center in ChennaiDelete
Do you really need an infinite list here? It seems that a simple accumulator would be more appropriate (I am not familiar with Haskell, so the below is Scheme):ReplyDelete
;; creates a Hydra with n heads
(define (hydra n)
(make-list n n)
;; chops off a single Hydra head with value X
;; head X is replaced with X - 1 heads of value X - 1
(define (chop h)
((null? h) '())
((= 1 (car h)) (cdr h))
(else (append (hydra (- (car h) 1)) (cdr h))))
;; count the number of chops it takes to kill a Hydra with N heads
(define (count-chops heads)
(let loop ((h heads)
(if (null? h)
(loop (chop h) (+ 1 acc)))))
;; computes 986409 in 1.57 seconds
Good Question :-). There are multiple ways of doing it. The solution you posted is the tail recursive version of the solution, which corresponds to the following haskell code (reusing the chop method from above)Delete
countToSlay heads = chopsCount 0 heads
where chopsCount acc  = acc
chopsCount acc heads = chopsCount (acc + 1) (chop heads)
Most functional programming languages, the performance of the two solutions should be similar. Uncompiled, the infinite list solution takes 1.01 seconds and the tail recursive one takes 1.63 seconds on my laptop. Compiled, they take 0.090s and 0.218 respectively.
The reason for this is because lists are lazy, and calculated just in time. Functional programming languages are incredibly good at managing memory and space for this. In fact, since `length' is the eventual consumer of the infinite list, I suspect that there would only be a few objects that actually exist at any given point, the rest would be marked for GC.
As far as intuitiveness goes, I think there are merits for both ways of doing things. Personally I prefer the iterative way of an infinite list as it's easier for me to extend on the solution (with the willHerculesDie method). The willHerculesDie method would also need to do the null check on heads, which for me is a form of duplication.
mcmillhj please see my comment below, the updated Haskell version does this in 0.003sDelete
I'm sure the scheme version would do comparably fast without using an intermediary list too :P
How long does your solution take for a 10 and 11 headed Hydra? Even the tail recursive version doesnt seem to perform that "well" for those cases.ReplyDelete
Without compiling, it takes me quite a while. Running it in GHCI takes 73.01 seconds.Delete
Compiling the output, I can do (countOfChops ) in 9.01 seconds.
And yes, sometimes the iterative solution is in fact faster than the tail recursive one.
The problem is not polynomial, so it's expected to grow fast with the input.
Hmm interesting. Well Scheme doesn't have the option of compiling that I know of so there is always going to be a little more run-time overhead. I am sure there are other optimizations that I didn't include. I wrote up a small thing about my solution if you interested: http://blog.hjm.im/how-many-chops-does-it-take-hercules-to-kill-an-n-headed-hydra/Delete
This comment has been removed by the author.ReplyDelete
Hi, why are you using lists? I love the tutorial, but the code is very slow. With the help of #haskell I was show you can do this without lists:ReplyDelete
chops 1 = 1
chops n = 1 + (n-1) * chops (n-1)
countToSlay = sum . map chops
main = print $ countToSlay 
Also, you could use a mutable vector if you need some type of container:
import Prelude hiding (read, length)
chop :: MVector (PrimState IO) Int -> Int -> IO Int
chop heads 0 = read heads 0
chop heads n = do
count <- read heads n
lower <- read heads (pred n)
write heads (pred n) (lower + n * count)
(+count) <$> chop heads (pred n)
main :: IO ()
main = do
heads <- new 12
set heads 0
write heads (pred 12) 1 -- there is 1 12-headed hydra
print =<< chop heads (pred 12)
I hope I don't come off as rude or unappreciative of the tutorial, I just don't want people to think Haskell is slow :)Delete
The counting solution will always be faster regardless of the language because you don't need to allocate space for data structures.Delete
@Cody no worries, always appreciate feedback.Delete
I suppose the goal of this post is more of how to approach functional programming, and not necessarily to solve this particular problem (which as you mentioned, does have a quick, closed form solution).
Concepts of immutability, mapping and reducing are what I was hoping to put forth in this blog post, hoping that it will give a taste for people to learn more.
Its great lore.......ReplyDelete
web designing course
A really good 101 article - well explained & super-clear variable names & functions.ReplyDelete
cho thuê nhà trọ
cho thuê phòng trọ
nhac san cuc manh
số điện thoại tư vấn pháp luật miễn phí
văn phòng luật
tổng đài tư vấn pháp luật
dịch vụ thành lập công ty trọn gói
lý thuyết trò chơi trong kinh tế học
đức phật và nàng audio
hồ sơ mật dinh độc lập audio
đừng hoang tưởng về biển lớn ebook
chiến thắng trò chơi cuộc sống ebook
bước nhảy lượng tử
ngồi khóc trên cây audio
truy tìm ký ức audio
mặt dày tâm đen audio
thế giới như tôi thấy ebook
Thở phào một hơi hắn cố gắng trấn tĩnh trở lại. Ngẫm nghĩ lại mọi chuyện gần đây, hắn cảm thấy mình cũng có chút biến thái, tà ác. Công tâm mà nói nếu chỉ muốn nữ nhân thì hoàn toàn không khó. Ít nhất là Liễu Thanh Nghi lúc nào cũng sẵn sàng lên giường với hắn. Nhưng hắn lại hết lần này đến lần khác rình coi, tự sướng với nội y…Hành vi này tại kiếp trước không là gì cả thế nhưng tại thời đại này thì lại có chút hèn mọn, bỉ ổi.
Mỗi lần xong chuyện hắn đều cảm thấy áy náy, cắn rứt. Nhưng mỗi lần chuyện phát sinh hắn lại hưng phấn, kích thích, thật không kìm chế nổi.
Lưu Phong hiểu được chính mình cũng có gì đó không bình thường.
Đương nhiên hắn hiểu được loại cảm giác này cũng không phải hoàn toàn do bản ý của chính mình mà còn có ngoại nhân tác động.
Căn cứ tình huống bây giờ thì việc tu luyện của chính mình rất có thể người khác sẽ biết được.
Lưu Phong muốn tìm Bạch Khiết để thụ giáo nhưng viên Tam Phân Quy Nguyên Đan trên cổ hắn không hề có phản ứng , mặc cho hắn có kêu gọi như thế nào đi nữa cũng không có động tĩnh gì.
“Lão bà này chẳng lẽ lại tự sướng ở trong đó?” Lưu Phong trào phúng nghĩ thầm trong lòng.
Trời chiều, Lưu Phong môt mình đi dạo trên đường, chuẩn bị đi gặp Ân Tố Tố thì hắn đột nhiên phát giác từ sau lưng truyền đến một cỗ khí thế lẫm liệt bức người.
Lưu Phong giật mình quay đầu nhìn lại.
Một trung niên nam tử đang chắp tay thản nhiên đứng sau lưng hắn, hai mắt bắn ra hàn quang lạnh lẽo nhìn hắn.
Lưu Phong cảm giác được nguy hiểm, tay đặt lên nhuyễn kiếm. Ánh mắt thầm đánh giá đối phương. Nam tử này nhìn qua chừng hơn ba mươi tuổi, dáng người cao lớn anh tuấn, mắt sáng mũi thẳng. Thần thái ung dung nhưng uy phong lẫm liệt….tóm lại vẻ bề ngoài của hắn so với Lưu Phong không hề
I like your theme of choice for web journal however need to recommend you for sharing some more data with respect to your subject so we can comprehend your idea all the more unmistakably.. live blogging platformReplyDelete
one of the website templates available on the internet. going to share it with my friends so that they can get an idea of latest website designsIOS Applications DevelopmentReplyDelete
The war between humans, orcs and elves continues earn to die . Lead your race through a series of epic battles, using your crossbow to fend off foes and sending out units to destroy castleshappy wheels . Researching and upgrading wisely will be crucial to your success! There are 5 ages total and each one will bring you new units to train to fight in the war for you cause.ReplyDelete
earn to die 2
Whatever you do, don’t neglect your home base because you cannot repair it and once it is destroyed, you lose! Age of War is the first game of the series and really sets the tone for the Age of War games . Also try out the Age of Defense series as it is pretty similar.
In this game, you start at the cavern men’s age, then evolvetank trouble ! There is a total of 5 ages, each with its units and turrets. Take control of 16 different units and 15 different turrets to defend your base and destroy your enemy.
The goal of the game also differs depending on the level. In most levels the goal is to reach a finish line or to collect tokens. Many levels feature alternate or nonexistent goals for the player. The game controls are shown just under gold miner. Movement mechanisms primarily include acceleration and tilting controls. cubefield
It consists of a total of 17 levels and the challenge you face in each level increases as you go up. unfair mario The game basically has a red ball that has to be moved across the various obstacles in its path to the goal. slitherio
A good blog. Thanks for sharing the information. It is very useful for my future. keep sharingReplyDelete
red ball 2 | duck life 2 | happy wheels | Red Ball | Red ball 3 | Flash Games| Tank trouble
Bug Fixes - Fixed the email when launched to application. check out this Heading makes it easy to get you out on the road, or sea, as quickly as possible.ReplyDelete
If Dan should get trapped, simply tap on him to end his current life. web site! - Add/edit/remove images, and access items you added using My Images.ReplyDelete
Swiping between stories: making it quicker to move from one story to the next. download videos As an App developer, you can use iTabChart to keep track of your products.ReplyDelete
Take control of where you are posting with the "Ask Where To Post" feature. downlodable keygens Feel free to test the accuracy against your car's trip odometer, it's FREE.ReplyDelete
For example, one fun game to play, is to try to make a specific design, like a letter, or number. This link Just shake your iPhone and let Keyshaker generate a key for you (full ASCII since version 1.ReplyDelete
If youre a list maker, or just someone who needs a little help in the organization department, TooDoo is here to help. downlodable freeware Charts are based on top currency / selected currency.ReplyDelete
Clear and pleasant voice guide spoken by native speakers. download files Share Investing & Stockbroking lets you view the market and trade.ReplyDelete
After various betas and release candidates numbered 1. handevent.ru Follow the most popular tricks of "Le Parkour":- Speed Vault.ReplyDelete
We will update this app on a regular basis with the suggestions from NurseNotes users. link for you Get food delivered even if you have NO IDEA where you are.ReplyDelete
An ever growing selection of topics packed with resources, including topics for popular children's books and stories. downloadfreefile.xyz You we see a flat map being wrapped into a cylinder (Mercator projection) and then transform into a globe.ReplyDelete
Thank you I hope you enjoy this mobile application. downloadtorrentfromnora.online Please update your reviewss after try this version.ReplyDelete
Device ID - We use this permission to get an ID of the device that is used to create the name of the pictures the experts users upload. iwanttodownload.gdn After the Singularity, everyone and everything is sentient and telepathic.ReplyDelete
Feel the swarm of playing pure casino slot machines whenever and whenever you want. http://gooddownloadsoftwarefast.pro You still have to select the registration icon and, if scouting for your team, the player you are scouting for.ReplyDelete
You can find the notes from the appointment of a day. downloadingstarted.top Add files using iTunes, direct link, from photo library or any cloud storage services, e.ReplyDelete
Seamless password management for your mobile devices. bestfromlydia.info Added support for images and passages Updated app badge Ready for 2015ReplyDelete
شركة تنظيف مكيفات بالرياضReplyDelete
شركة تنظيف شقق بالرياض
شركة تنظيف مجالس بالرياض
شركة تنظيف خزانات بالرياض
شركة عزل خزانات بالرياض
شركة تسليك مجارى بالرياض
Mua vé tại đại lý vé máy bay Aivivu, tham khảoReplyDelete
vé máy bay đi Mỹ giá bao nhiêu
vé máy bay hà nội sài gòn tháng 12
mua vé máy bay cần thơ - hà nội
giá vé máy bay hà nội đi nha trang
gia ve may bay tphcm di quy nhon
taxi ở sân bay nội bài
combo khách sạn phú quốc
rastgele görüntülü konuşma - kredi hesaplama - instagram video indir - instagram takipçi satın al - instagram takipçi satın al - tiktok takipçi satın al - instagram takipçi satın al - instagram beğeni satın al - instagram takipçi satın al - instagram takipçi satın al - instagram takipçi satın al - instagram takipçi satın al - binance güvenilir mi - binance güvenilir mi - binance güvenilir mi - binance güvenilir mi - instagram beğeni satın al - instagram beğeni satın al - polen filtresi - google haritalara yer ekleme - btcturk güvenilir mi - binance hesap açma - kuşadası kiralık villa - tiktok izlenme satın al - instagram takipçi satın al - sms onay - paribu sahibi - binance sahibi - btcturk sahibi - paribu ne zaman kuruldu - binance ne zaman kuruldu - btcturk ne zaman kuruldu - youtube izlenme satın al - torrent oyun - google haritalara yer ekleme - altyapısız internet - bedava internet - no deposit bonus forex - erkek spor ayakkabı - webturkey.net - karfiltre.com - tiktok jeton hilesi - tiktok beğeni satın al - microsoft word indir - misli indirReplyDelete
tiktok jeton hilesiReplyDelete
tiktok jeton hilesi
referans kimliği nedir
gate güvenilir mi
tiktok jeton hilesi
bitcoin nasıl alınır
İnstagram takipçi satın al! İnstagram takipçi sitesi ile takipçi satın al sende sosyal medyada fenomen olmaya bir adım at. Sende hemen instagram takipçi satın almak istiyorsan tıkla:ReplyDelete
1- takipçi satın al
2- takipçi satın al
3- takipçi satın al
Eminent . Kindly continue to compose more on this subject . I need more material on this point. What is the Kenya visa cost for US citizens ? The visa expenses for Kenya are no different for all nations . It is just impacted by the sort of e visa which one you select. .ReplyDelete
Very nice . thankyou, Finally I reached that article . Which I was trying to find for many days. Do you know how to get a Vietnam e visa ? Yes, I know and this process is very simple . you only need to apply online and pay online.ReplyDelete
Amazingly unimaginable really, these blogs are very attractive. How to apply e visa India? Apply online , pay online and get your visa online in your updated email. Id.
You will notice the phrases wilds and scatters mentioned often on our website. These refer to the special symbols you'll come across in all our slot games. They will slowly become your favorite, and you will want to|it can be greatest to|you'll want to} pay attention to|take note of} them, as they'll unlock some hidden bonus features inside the slot games. Our carefully thought-out selection of titles 바카라사이트 doesn’t simply value quantity. To prove this, the next part will cover a few of the the} most popular games amongst our British members.ReplyDelete