I am struggling to think of a way to utilize these functions for this beginner level coding class that I am taking to learn functional programming in Haskell. The functions I have to write are shown below, asum
is supposed to turn a list of integers [a1,a2,..,an]
into the alternating sum a1-a2 a3-a4 .…
and I am not sure how to approach it with these functions. The xor
function is supposed to that computes the XOR of a list of Booleans. I need some help to understand how to use these functions and it would greatly appreciated. I am also new to Haskell so any explanations would help. Thanks I have to use map foldr foldl
.
asum :: (Num a) => [a] -> a
xor :: [Bool] -> Bool
CodePudding user response:
Here's an idea:
a1-a2 a3-a4 ...
=
a1-(a2-(a3-(a4-(...(an-0)...))))
This fits pretty well to the foldr
pattern of recursion,
foldr f z [a1,a2,a3,a4,...,an]
=
a1`f`(a2`f`(a3`f`(a4`f`(...(an`f`z)...))))
So it can be coded by setting f = ...
and z = ...
and calling
asum :: (Num a) => [a] -> a
asum xs = foldr f z xs
where
f = (...)
z = (...)
You will need to complete this definition.
For the XOR
of a list of Booleans, assuming it is to be True
if one and only one of them is True
, and False
otherwise, we can imagine this sequence of transformations:
[ True, False, False, True, True, False, ...]
==>
[ t, f, f, t, t, f, ...]
where t
and f
are some specially chosen numbers. And then we can find the sum of this second list (not alternating sum, just a sum of a list of numbers) and check whether it is equal to ... some (other?) special number, let's call it n1
:
xor :: [Bool] -> Bool
xor bools = (aNumber ... n1)
where
list1 = bools
list2 = fun1 transform list1
transform False = f
transform True = t
f = ...
t = ...
aNumber = sum list2
n1 = ...
fun1 = ...
sum listOfNums = ...
fun1
is the function which transforms each element of its argument list according to the given function, called transform
above. It is one of the two functions left from the three you were given, considering we've already been using foldr
.
sum
is to be implemented by using the last function that's left.
FYI,
map foo [a1,a2,a3,...,an]
=
[foo a1, foo a2, foo a3, ..., foo an]
and
foldl f z [a1,a2,a3,...,an]
=
((((z`f`a1)`f`a2)`f`a3)...)`f`an
CodePudding user response:
I would say start by running the following, one by one, in GHCi
:
:t foldr
:info foldr
:doc foldr
:t foldl
:info foldl
:doc foldl
:t map
:info map
:doc map
Or better, open hoogle.haskell.org and search each of the above mentioned functions and click on the first link.
But I agree that Haskell documentation are difficult to read, especially for beginners. I'm a beginner and I have a lot of difficulty reading and understanding them.
Here's a function that uses map
and foldr
to show how foldr
works:
printFoldr xs = foldr (\x acc -> "(" x " " acc " )") "0" $ map show xs
Now running watch this:
printFoldr [1..5]
-- outputs the following:
"(1 (2 (3 (4 (5 0 ) ) ) ) )"
This shows us how foldr
is evaluated. Before going into how foldr
is evaluated, let's look briefly at map
.
map show [1..5]
-- outputs the following:
["1","2","3","4","5"]
This means that map
takes 2 arguments. A list and a function that is applied to each element of the list. The result is a new list with the function applied to each element. Thus, applying show
to each number outputs their string representation.
Back to foldr
. foldr
takes 3 arguments:
- a function of type
a -> b -> b
- an initial value of type
b
- a list of type
[a]
foldr
takes each and every value of the provided list and applies this function to it. What is special is that map retains the output of the function over each iteration and passes it to the function as its second argument on the next run. Therefore it is convenient to write the function that is passed foldr
as follows: (\el acc -> do something)
. Now on the next iteration of foldr
, acc
will hold the value of the previous run and el
will be the current element from the list. BTW, acc
stands for accumulator and el
for element. This enables us to reduce elements of the provided list to something completely new.
As you can see in printFoldr
, the initial value is just an empty string but it gradually adds the lists elements to it showing how it would have reduced the elements of the list to their sum.