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
The ++ operator is the list concatenation operator which takes two lists as operands and "combine" them into a single list.
'||': 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.
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).
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.))
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With