Friday, December 6, 2013

Looping in Haskell

When I first started out with Haskell, some things were made very clear: it was a pure language, it was expressive, and it told what data was, not what it did. However, coming from imperative languages like Java and C, I found myself wanting to know how to loop in Haskell. This was a basic want, because looping is one of the big concepts in programming those languages (along with conditionals and blocking). So, here are some correct ways to "loop" in Haskell, using higher-order functions and recursion.


Tail Call Recursion
Tail Call Recursion is a particularly efficient method of traversing data. The basic structure of a tail-recursive function is:

  1. Check the base-case
  2. Perform some action
  3. Set up the tail call.
The base case is what happens when you no longer want to recurse. If you're moving over a list of Ints, adding 1 to everything, this could be when the list is [] (empty).

In this case, the action would be adding one to a value, and appending it to the next call of the function.

The tail-call would then be the same function, but with the head of the list cut off.

The add-one-to-all numbers function would look something like this:

add-one-to-all :: [Int] -> [Int]
add-one-to-all [] = []
add-one-to-all (x:xs) = 1 + x : add-one-to-all xs

Here, when the list pattern matches [] (an empty list), an empty list is returned. Only when this happens will the function "snap back", collecting the other values from the list.

Higher-Order Functions
The entire point of a higher-order function is to be able to pass functions as parameters to other functions, or to return them from functions. In traversing a list, for instance, you could make a function that takes a function and a list, and then apply that with a function that adds one to a number.

traverse :: (a -> b) -> [a] -> [b]
traverse _ [] = []
traverse f (x:xs) = f x : traverse xs

add-one :: Int -> Int
add-one x = x + 1

add-one-to-all :: [Int] -> [Int]
add-one-to-all x = traverse add-one x

Here, you can see that the function "f" of traverse (type: (a -> b)) is applied recursively to a list. a and b are just type parameters, which are helpful for generic abstractions like this. Then, add-one is defined, and finally mapped over the list in add-one-to-all. The function "traverse" actually already exists in Prelude as the function map.

A bit extra
Haskell does something called currying, which allows the partial application of functions. Discussion on currying is outside the scope of this simple tutorial, but here is a very small implementation of add-one-to-all

add-one-to-all :: [Int] -> [Int]
add-one-to-all = map (+1)

5 comments:

  1. With millions of active users, Hotmail is yet another email client that comes with many exciting features. So if you are looking for Hotmail tech support to resolve any difficulty that you are facing while creating the account, resetting the account and many more, you can go for Hotmail customer service at 0800-029-4639.
    Hotmail Help Number UK

    ReplyDelete
  2. The user of Gmail does not have to look for any other support service. All the engineers make sure that problems or confusion will be resolved in a simple way. For this user should make good use of Gmail Support Number UK and retrieve answers for queries like – emails are bouncing back, difficulty in the setting of profile pictures, unsubscribing of emails is not possible etc.

    ReplyDelete
  3. Hotmail users have to face many difficulties since Hotmail has turned into Outlook.com. Although, it is simple to sign in to your Hotmail account using Outlook but still, if you are getting any issue in the process then feel free to contact us at Hotmail Helpline Number UK .
    Contact: - 0808-169-1988
    Address: - London UK
    Website: - http://www.uk-help.co.uk/hotmail-service.php

    ReplyDelete
  4. If for any reason you are not able to access your Gmail account, and then dial Gmail Customer Care Number UK for assistance. We will diagnose the issue and then provide you with an appropriate solution to rectify the problem.
    Contact No. : - 0808-169-9742
    Website: - http://www.gmail-support.uk/gmail-support.php
    Face Book: - https://www.facebook.com/gmailuksupport/
    Twitter: - https://twitter.com/gmailuknumber
    Instagram: - https://www.instagram.com/i_am_rosie_taylor/
    Address: - London, United Kingdom

    ReplyDelete
  5. There can be multiple reasons behind Hotmail giving the error message “something went wrong” such as the problem can be related to syncing of account with the Hotmail server, it can also be the browser issue or it can be the issue related to the network if needed then to know more the user should get in touch with the certified Hotmail technicians they can be asked for help as and when needed at +44-800-368-9064.
    Hotmail Helpline Number UK

    ReplyDelete