Getting gcd list

Question

I am new to Haskell, in fact I have just started, and I would like to get a little hint at the question that I am going to ask.

I am currently trying to get the GCD of this list. For example, having a list [3, 6, 9], it will return 3.

At the moment, I take the following approach, am I going in a good direction?

let getGCD l = map (\xy -> gcd xy) l 

Answer 1

Not really, you don't want a map , but rather a fold. map allows you to convert each element to a list evenly, so you give it a local transform a -> b and it gives a global transform ( [a] -> [b] ). This is not what you want.

As a quick primer on the folds, there is a whole family of them, which allows us to express the calculations that we create by re-applying the function to the initial value, the next element and list, and then repeating this application with the result as a new initial value. So foldl' (+) 0 [1, 2, 3, 4] will be something like

  foldl' (+) 0 [1, 2, 3, 4] ==> foldl' (+) 1 [2, 3, 4] ==> foldl' (+) 3 [3, 4] ==> foldl' (+) 6 [4] ==> foldl' (+) 10 [] ==> -- For empty lists we just return the seed given 10 

Can you figure out how to postpone the problem in this structure?

Additional Tips

You want to take a list and calculate the result, which depends on each element of the list, something like

 gcdAll :: [Int] -> Int gcdAll l = foldl' step initial l 

closer to what you want, where step takes the current gcd of the list you have processed so far, and the next element of the list and returns the next value, and the initial one is the value that starts with (and that returns if l empty Since there is actually no normal value, I would divide it into

 gcdAll :: [Int] -> Maybe Int gcdAll [] = Nothing gcdAll (h : rest) = Just $ foldl' step h rest 

so that you correctly signal the possibility of failure, after all, that gcd is nothing?

Note that foldl' imported from Data.List .

Answer 2

You can recursively use gcd in a list (essentially an implementation of addition)

 gcd' :: (Integral a) => [a] -> a gcd' [] = 1 gcd' [x] = x gcd' (x:xs) = gcd x (gcd' xs) 

Answer 3

A GCD is a property of a pair of numbers. So, really, you want to look at pairs of numbers taken from your list. Ultimately, you want one GCD for the entire list, but as a first step you need pairs.

There is a well-known trick for working with serial pairs:

 f1 list = zipWith f2 list (tail list) 

The zipWith function zipWith bit like map , but works with a couple of lists. In this case, the source list and tail of the source list. (Note that this fails if the list is empty.) If you replace f2 your gcd function, you now have a new list, which is the GCD of each consecutive pair of numbers. And this list is one element shorter than the original:

 f1 [x, y, z, w] ==> [gcd xy, gcd yz, gcd zw] 

Therefore, every time you apply f1 to a list, you get a new, shorter GCD list. Apply it enough time and you should only get one item ...