Solve the algorithmic problem with an end recursive form-CodePudding

Input: List xs with arbitrary numeric elements, xs has at least two elements / Output: smallest distance between adjacent elements in the list.

-- Input: List xs with at least two numeric elements & its implementation an end recursive function. -- Erg: Returns the smallest distance of adjacent elements from the output list.

minimumdistance :: [Int] -> Int
minimumdistance [] = error "Empty list".
minimumdistance [_] = error "Requirement is not met".
minimumdistance [a,b] = abs (a - b)
minimaldistance (x:y:xs) = helper (abs (x - y)) xs where 
   helper :: Int -> [Int] -> Int 
   helper acc [] = acc
   helper acc (z:zs) = if (abs (y - z)) < acc then helper (abs (y - z)) zs else helper 
   acc zs

Is the function endrecursive because that we are supposed to solve the task endrecursive and I am sure because I do not have the definition yet correctly, but I also on other pages, the endrecursive representation not understood

CodePudding user response：

Your code has several issues mentioned in comments.

I suggest you break this down into smaller problems. We can write a tail-recursive function to get pairs of adjacent numbers from the list.

pairs [] = error "Not long enough"
pairs [_] = error "Not long enough"
pairs lst = aux lst []
 where
  aux (a:b:c) acc = aux (b:c) ((a, b):acc)
  aux _ acc = acc

Now, if we test this:

ghci> pairs [1, 3, 6, 7, 10]
[(7,10),(6,7),(3,6),(1,3)]

We can use map to get the differences.

ghci> map (\(a, b) -> abs (a - b)) $ pairs [1, 3, 6, 7, 10]
[3,1,3,2]

Now we just need to reduce that down to the minimum.

ghci> foldl1 min $ map (\(a, b) -> abs (a - b)) $ pairs [1, 3, 6, 7, 10]
1

CodePudding user response：

In your code for the helper function, the y variable does not get updated at all. Hence it remains equal to the second element of the initial input list in all successive scopes. This is probably not what you want.

It is more reliable to just include the previous list element into your state/accumulator, together with the smallest distance seen so far. This gives the following code:

minimumDistance :: [Int] -> Int
minimumDistance []       =  error "Empty list."
minimumDistance [_]      =  error "Requirement is not met."
minimumDistance (x:y:xs) =  helper  (abs (x-y), y)  xs  where
        helper (mnd,u)  []     =  mnd
        helper (mnd,u) (z:zs)  =  let  d1 = abs (u-z)
                                  in   if (d1 < mnd)  then  helper (d1,  z)  zs
                                                      else  helper (mnd, z)  zs

Sanity check:

We can generate a small random list, and compare the result of our minimumDistance function with the one obtained by just combining a few suitable library functions. Like this:

$ ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/  :? for help
...
 λ> 
 λ> :load q75011741.hs
 [1 of 1] Compiling Main             ( q75011741.hs, interpreted )
 Ok, one module loaded.
 λ> 
 λ> :type minimumDistance
 minimumDistance :: [Int] -> Int
 λ> 
 λ> import System.Random (randomRs, mkStdGen)
 λ> 
 λ> g0 = mkStdGen 42
 λ> 
 λ> xs = take 20 $ randomRs (0,500) g0
 λ> 
 λ> xs
 [48,151,95,271,208,466,401,23,139,95,500,306,187,389,398,297,248,94,348,91]
 λ> 
 λ> minimumDistance xs
 9
 λ> 
 λ>
 λ> zip xs (tail xs)
 [(48,151),(151,95),(95,271),(271,208),(208,466),(466,401),(401,23),(23,139),(139,95),(95,500),(500,306),(306,187),(187,389),(389,398),(398,297),(297,248),(248,94),(94,348),(348,91)]
 λ> 
 λ> map (\(a,b) -> abs(a-b)) $ zip xs (tail xs) 
 [103,56,176,63,258,65,378,116,44,405,194,119,202,9,101,49,154,254,257]
 λ> 
 λ> minimum $ map (\(a,b) -> abs(a-b)) $ zip xs (tail xs) 
 9
 λ>

So it looks OK.