tags:

views:

427

answers:

3

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?

+15  A: 

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 _        = []
bdonlan
+14  A: 

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.

Justice
Just a word on that underscore `_` in the `fact (x:_:xs)` code snippet, which extracts the second element of the list. Since it is going to be thrown out anyway, it would be silly to assign the second element a useless variable name. The underscore is just a way of letting Haskell know to select the second element, regardless of what it is, without bothering to assign it a variable name, making the code quite readable in my opinion.
Zaid
I think there is also another reason why we do not use the "length" solution. Not only the efficiency. The task You specified is meaningful also for infinite lists. Working with infinite lists is not just a sophism, because Haskell's lazy nature can provide approaches, where working with infinite lists can be justified. The "length"-using solution works only for finite lists, while the "lazier" approaches work both for infinite and finite lists. OFF: Sometimes,lazy evaluation can provide approaches which are very powerful and unintuitive (`magical'), e.g. circular programming, repmin problem.
physis
+1  A: 

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 mth 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 mth", 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
physis