Multiple Statements In Haskell

Question

How do you have multiple statements in haskell?

Here's what I'm trying to do: given a list such as [a,b,c,d], return every other element, so you get [a,c]. I can see the solution, and here's what I have so far:

fact (xs)   | length( xs ) `mod` 2  == 1 = head( xs )
 | otherwise = fact(tail( xs ))

This works fine the first time around, but then it quits. What I want to be able to say is return the head, and then call fact(tail(xs)) How do I do that?

Answer 1

The function you specified returns only a single element. You'd need to change it to something like:

fact [] = [] -- can't call tail on a list of length 0!
fact (xs)   | length( xs ) `mod` 2  == 1 = head( xs ) : fact(tail(xs))
            | otherwise = fact(tail( xs ))

You may find it helpful to write out type signatures to help figure out thinkos like this:

fact :: [a] -> [a] -- convert a list of anything to another (shorter) list

However note that this is very slow - O(n^2) in fact, since it's taking length at each step. A much more haskelly solution would use pattern matching to process two elements at a time:

fact :: [a] -> [a]
-- Take the first element of each two-element pair...
fact (x:_:xs) = x:fact xs
-- If we have only one element left, we had an odd-length list.
-- So grab the last element too.
fact [x]      = [x]
-- Return nothing if we have an empty list
fact _        = []

Answer 2

There are no statements in Haskell.

You should not abuse parentheses in Haskell. Rather, you should accustom yourself to the language. So your original code should look like

fact xs | length xs `mod` 2 == 1 = head xs
        | otherwise              = fact (tail xs)

As bdonlan notes, the function you are looking for is really

fact []       = []
fact [x]      = [x]
fact (x:_:xs) = x : fact xs

Suppose we have the list [a, b, c, d]. Let us apply the function and fully evaluate the result.

fact [a, b, c, d] = a : fact [c, d]
                  = a : c : fact []
                  = a : c : []
                  = [a, c]

Note that [a, b, c, d] is exactly the same as a : b : c : d : [] because the two ways of representing lists are interpreted interchangeably by the compiler.

Answer 3

Swapping a semaphore

In fact, we can do it following two possible patterns:

• [1,2,3,4,..] becomes [1,3,5,7...]
• [1,2,3,4,..] becomes [2,4,6,8...]

Both do the same, but they "begin the counting" the opposite way. Let us implement both of them with the same function! Of course, this function must be parametrized according to the "pattern". Two possible patterns exist, thus, we need a boolean for type for parametrization. Implementation: let us use a boolean parameter as a "flag", "semaphore":

module Alternation where

every_second :: [a] -> [a]
every_second =  every_second_at False

every_second_at :: Bool -> [a] -> [a]
every_second_at _ [] = []
every_second_at True  (x : xs) = x : every_second_at False xs
every_second_at False (x : xs) =     every_second_at True xs

We have used an auxiliary function, bookkeeping the "flag/semaphore": it is swapping it accordingly. In fact, this auxiliary function can be regarded as a generalization of the original task. I think, that is what is called a "worker wrapper" function.

Countdown with an index

The task can be generalized even further. Why not to write a much more general function, which can be parametrized by a "modulus" m, and it "harvests" all m^th elems of a list?

• every_mth 1 [1,2,3,4,...] yields [1,2,3,4...]
• every_mth 2 [1,2,3,4,...] yields [1,3,5...]
• every_mth 3 [1,2,3,4,...] yields [1,4,7...]

We can use the same ideas as before, just we have to use more complicated a "semaphore": a natural number instead of a boolean. This is a "countdown" parameter, an index i bookkeeping when it is our turn:

module Cycle where

import Nat (Nat)

every_mth :: Nat -> [a] -> [a]
every_mth 0           = undefined
every_mth m @ (i + 1) = every_mth_at m i

We use an auxiliary function (worker wrapper), bookkeeping the countdown index i:

every_mth_at :: Nat -> Nat -> [a] -> [a]
every_mth_at _       _ []       = []
every_mth_at m 0       (x : xs) = x : every_mth m xs
every_nth_at m (i + 1) (x : xs) =     every_mth_at m i xs

For simplicity's sake, natural number type is "implemented" here as a mere alias:

module Nat (Nat) where

type Nat = Integer

Maybe, in a number theoretic sense, there are also cleaner alternative approaches, not exactly equivalent to the task You specified, but adjusting seems to be straightforward:

• let every_mth 1 [0,1,2,3,4,...] yield [0,1,2,3,4,...]
• let every_mth 2 [0,1,2,3,4,...] yield [0,2,4,6,8...]
• let every_mth 3 [0,1,2,3,4,...] yield [0,3,6,9...]

thus, it is specified here so that it should provide "incidentally" the list of multiples of the parameter, when applied to the lazy list of all natural numbers.

In its implementation, it is worth using numbers as a "zero-based" index. Instead of "every m^th", we say: "use i as an index ranging 0, 1, ..., u = m-1, where u denotes the upper limit of the possible indices. This upper index can be a useful parameter in the auxiliary function, which counts down the index.

module Multiple where

import Nat (Nat)

every_mth :: Nat -> [a] -> [a]
every_mth 0  = undefined
every_mth (u + 1) = countdown u

countdown :: Nat -> [a] -> [a]
countdown = countdown_at 0

countdown_at :: Nat -> Nat -> [a] -> [a]
countdown_at _       _ []       = []
countdown_at 0       u (x : xs) = x : countdown_at u u xs
countdown_at (i + 1) u (x : xs) =     countdown_at i u xs