Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Better way to write the following program in Haskell

Tags:

haskell

I'm writing a function that reduce free words. One can consider it as the following algorithm:

The idea is to cancel items in the list, if they are negative of each other and adjacent to each other. Apply it repeatedly until there is no more to cancel. For example [-2,1,-1,2,3] -> [-2,2,3]->[3]

I wrote the following code. It doesn't seem elegant. It uses head, tail many times, and there are total of 3 patterns for this function's input, it be nice if it can be reduced to 2. I want to know if there are more elegant ways to write it in Haskell. I suspect I can use fold for this, but I don't see how to do it naturally.

freeReduce []  = []
freeReduce [x] = [x]
freeReduce (x:xs)
  | x == -(head xs) = freeReduce (tail xs)
  | otherwise       = if' (rest == [])
                          [x]
                          (if' (x == - (head rest)) (tail rest) (x:rest))
  where rest = freeReduce xs
like image 428
Chao Xu Avatar asked Jun 25 '11 06:06

Chao Xu


People also ask

What does ++ mean in Haskell?

The ++ operator is the list concatenation operator which takes two lists as operands and "combine" them into a single list.

How do you write or in Haskell?

'||': We use one defined symbol to represent the or operator in Haskell, which is represented by the double pipe '||'. This symbol should be present in every condition we have. so on this basis, it will return us the result.

How do you write a main function in Haskell?

The type of main in Haskell is almost always IO () which tells us that main does input/output and its only “return value” is output to a screen or some other kind of effect (in this program, the effect is printing the result of the function evaluation to the screen).


1 Answers

This is the clearest I can make it:

freeReduce []       = []
freeReduce (x : xs) = case freeReduce xs of
                           y : ys | y == -x ->     ys
                           ys               -> x : ys

Or equivalently:

freeReduce = foldr f []
  where f x (y : ys) | y == -x =     ys
        f x ys                 = x : ys

(Both untested.)

It seems that freeReduce is inherently strict.

(My original, incorrect attempt:

freeReduce (x : y : rest) | x == -y =     freeReduce rest
freeReduce (x : rest)               = x : freeReduce rest
freeReduce []                       =     []

(Untested.))

like image 52
dave4420 Avatar answered Sep 21 '22 22:09

dave4420