-1

I have to write an Haskell function shiftToZero :: (Num a, Ord a) => [a] -> [a] that given a list constructs a new list that contains the elements decreased by the minimum value.

The function should not visit list elements more than once (take advantage of laziness).

For example: shiftToZero [5,4,2,6] -> [3,2,0,4]

Any suggestion to resolve this?

rik99
  • 9
  • 1
  • 1
    Unless this is one of those brain-melting "tie the knot" problems, you can't produce the first element of `shiftToZero xs` without scanning all of `xs` first to find the value you'll subtract from `head xs`. – chepner Mar 09 '23 at 16:52
  • You might be interested in [Why Attribute Grammars Matter](https://wiki.haskell.org/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter). – Noughtmare Mar 09 '23 at 16:53
  • 2
    @chepner There is indeed a brain-melting tie-the-knot solution. – Daniel Wagner Mar 09 '23 at 17:27
  • Note that in Haskell we can write things like `f x = b where (a,b) = (2*x,a+3)` which is a weird way to write `f x = 2*x+3`. Thanks to laziness, the recursive pair definition doesn't diverge but produces two values even if the second component of the result depends on the first one. In your case you might use something similar except `(a,b) = ...` will have a more complex expression on the right hand side. – chi Mar 09 '23 at 21:43
  • Related: [*Catamorphism that allows looking at part of the final result*](https://stackoverflow.com/q/56121207/2751851) – duplode Mar 10 '23 at 00:09
  • @Noughtmare you saved me, I didn't know the "tie the knot" method. – rik99 Mar 10 '23 at 10:13

1 Answers1

1

I'll give a hint, by way of a simpler problem to solve first. I would like to have a helper function with the type helper :: (Num a, Ord a) => (a, [a]) -> (a, [a]). The helper should return the same answer as this function:

inefficientHelper (x, xs) = (minimum xs, map (\x' -> x'-x) xs)

The problem with inefficientHelper is that it computes its two answers in two separate passes, so it could never be a component that we could use in implementing the function you care about. So your first task is to implement helper to return the right value (as specified by this inefficient implementation), but while making only one pass over the list xs.

Presumably this is being given as an exercise in some teaching material, and so the most recent material will have other examples of tying the knot that can serve as a hint for what comes after that. But if not, then have a Google -- there's lots of writing floating around on "tying the knot".

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380