Haskell: Minimum sum of list

Question

So, I'm new here, and I would like to ask 2 questions about some code:

1. Duplicate each element in list by n times. For example, duplicate [1,2,3] should give [1,2,2,3,3,3]

   duplicate1 xs = x*x ++ duplicate1 xs
   

   What is wrong in here?

2. Take positive numbers from list and find the minimum positive subtraction. For example, [-2,-1,0,1,3] should give 1 because (1-0) is the lowest difference above 0.

Answer 1

Here, this should do the trick:

dup [] = []
dup (x:xs) = (replicate x x) ++ (dup xs)

We define dup recursively: for empty list it is just an empty list, for a non empty list, it is a list in which the first x elements are equal to x (the head of the initial list), and the rest is the list generated by recursively applying the dup function. It is easy to prove the correctness of this solution by induction (do it as an exercise).

Now, lets analyze your initial solution:

duplicate1 xs = x*x ++ duplicate1 xs

The first mistake: you did not define the list pattern properly. According to your definition, the function has just one argument - xs. To achieve the desired effect, you should use the correct pattern for matching the list's head and tail (x:xs, see my previous example). Read up on pattern matching.

But that's not all. Second mistake: x*x is actually x squared, not a list of two values. Which brings us to the third mistake: ++ expects both of its operands to be lists of values of the same type. While in your code, you're trying to apply ++ to two values of types Int and [Int].

As for the second task, the solution has already been given.

HTH

Answer 2

1) You can use the fact that list is a monad:

dup = (=<<) (\x -> replicate x x)

Or in do-notation:

dup xs = do x <- xs; replicate x x; return x

2) For getting only the positive numbers from a list, you can use filter:

filter (>= 0) [1,-1,0,-5,3]
-- [1,0,3]   

To get all possible "pairings" you can use either monads or applicative functors:

import Control.Applicative
(,) <$> [1,2,3] <*> [1,2,3]
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

Of course instead of creating pairs you can generate directly differences when replacing (,) by (-). Now you need to filter again, discarding all zero or negative differences. Then you only need to find the minimum of the list, but I think you can guess the name of that function.

Answer 3

To your first question:

• Use pattern matching. You can write something like duplicate (x:xs). This will deconstruct the first cell of the parameter list. If the list is empty, the next pattern is tried:

   duplicate (x:xs) = ... -- list is not empty
   duplicate []     = ... -- list is empty
  

• the function replicate n x creates a list, that contains n items x. For instance replicate 3 'a' yields `['a','a','a'].

• Use recursion. To understand, how recursion works, it is important to understand the concept of recursion first ;)

Answer 4

For your first part, there are a few issues: you forgot the pattern in the first argument, you are trying to square the first element rather than replicate it, and there is no second case to end your recursion (it will crash). To help, here is a type signature:

replicate :: Int -> a -> [a]

For your second part, if it has been covered in your course, you could try a list comprehension to get all differences of the numbers, and then you can apply the minimum function. If you don't know list comprehensions, you can do something similar with concatMap.

Don't forget that you can check functions on http://www.haskell.org/hoogle/ (Hoogle) or similar search engines.

Tell me if you need a more thorough answer.

Answer 5

1)

dupe :: [Int] -> [Int]
dupe l = concat [replicate i i | i<-l]

Theres a few problems with yours, one being that you are squaring each term, not creating a new list. In addition, your pattern matching is off and you would create am infinite recursion. Note how you recurse on the exact same list as was input. I think you mean something along the lines of duplicate1 (x:xs) = (replicate x x) ++ duplicate1 xs and that would be fine, so long as you write a proper base case as well.

2)

This is pretty straight forward from your problem description, but probably not too efficient. First filters out negatives, thewn checks out all subtractions with non-negative results. Answer is the minumum of these

p2 l = let l2 = filter (\x -> x >= 0) l 
        in minimum [i-j | i<-l2, j<-l2, i >= j]

Problem here is that it will allow a number to be checkeed against itself, whichwiull lend to answers of always zero. Any ideas? I'd like to leave it to you, commenter has a point abou t spoon-feeding.