2

I am writing a recursive function called threeN that takes a list with one element and adds a new number depending on if it's even or odd. If it's even divide it by 2, and if it's odd multiply it by three and subtract 1. I'm having trouble with my base case which will check the list to see if an element is already contained in the list.

It should be like this:

prelude> threeN [9]
[14,5,10,20,7,14,28,56,19,38,13,26,9]

But Instead I get this:

prelude> threeN [9]
[9]

This is my code so far:

threeN :: [Integer] -> [Integer]
threeN [] = []
threeN [n]
    | n `elem` [n] = [n]
    | n `mod` 2 ==0 = threeN[n `div` 2] ++ [n]
    | n `mod` 2 ==1 = threeN[(3*n)-1] ++ [n]

This is supposed to be done with basic functions, so I can't use very advanced ones to solve the issue, which is why I'm having trouble.

6
  • 3
    Your code matches the line 9 `elem` [9] = [9] so it just returns [9] Commented Oct 4, 2018 at 2:16
  • I realized this is the issue but the trouble im having is coming up with a comparison that won’t return the beginning of the function. Commented Oct 4, 2018 at 4:33
  • How does the description of the intended behaviour relate to the example? The example looks like it's using the output from one step as input to the next step, but if that's the case, why does it stop after 12 iterations? Commented Oct 4, 2018 at 5:44
  • @MarkSeemann The example stops at 12 iterations since the front of the list (14) had already occurred once in the list. Commented Oct 4, 2018 at 5:46
  • Why is the second to last element in the example list 26 instead of 28? 9 is odd, so 9*3+1=28? Am I missing something? Commented Oct 4, 2018 at 6:41

4 Answers 4

3

Even if you can only use basic functions, it still helps if you can decompose the problem into smaller problems. Based on the OP and the comments thread, it seems that these three requirements must be fulfilled:

  • Calculate a number based on a previous number
  • Generate a list where the next element is based on the previous element
  • Stop generating when a duplicate is encountered

I'd suggest solving each of these problems independently of each other, and then combining the solutions.

Calculate the next number

At first glance, this seems to be the heart of the problem. This is where you need to detect whether the number is even or odd, and calculate a result accordingly. Implement this as a function that you could call, say, calcNext. It needs to have a type like this:

Prelude> :t calcNext
calcNext :: Integral a => a -> a

With it, you can calculate the next number based on any input:

Prelude> calcNext 9 
26
Prelude> calcNext 26
13
Prelude> calcNext 13
38
Prelude> calcNext 38
19

I'll leave the implementation of calcNext as an exercise.

Generate a list

Sometimes, it can be helpful to look for existing functions. Perhaps there's already a function that can be used to generate a list from a function like calcNext.

One way to look for such functions is to use Hoogle.

Making a guess and typing (a -> a) -> [a] into the search field on Hoogle yields a number of results, among which is iterate, which has the similar (but not identical) type of (a -> a) -> a -> [a]. That seems to be close enough, because it enables you to kick off list generation like this:

Prelude> take 10 $ iterate calcNext 9
[9,26,13,38,19,56,28,14,7,20]

Here I chose to take 10 because iterate will go on forever.

The order here is reversed compared to the OP, but I'll leave it as another exercise to reverse a (finite) list, if the order matters.

If you want to base a solution entirely on functions you wrote yourself, you can try to implement your own iterate function. If you need a hint, then you can always peek at the source code of the built-in iterate function - it's open source.

Stop on duplicate

This one is probably the trickiest part, since you need to 'remember' all the previous elements. What you can do is to create a function that not only calculates the next element, but also keeps a list of all previous elements around. You could write a wrapper function around calcNext that has a type like this:

Prelude> :t calcNextAcc
calcNextAcc :: Integral a => (a, [a]) -> (a, [a])

Since this function still returns the same type as its input, you can still use it with iterate:

Prelude> take 15 $ iterate calcNextAcc (9, [])
[(9,[]),(26,[9]),(13,[26,9]),(38,[13,26,9]),(19,[38,13,26,9]),(56,[19,38,13,26,9]),
 (28,[56,19,38,13,26,9]),(14,[28,56,19,38,13,26,9]),(7,[14,28,56,19,38,13,26,9]),
 (20,[7,14,28,56,19,38,13,26,9]),(10,[20,7,14,28,56,19,38,13,26,9]),
 (5,[10,20,7,14,28,56,19,38,13,26,9]),(14,[5,10,20,7,14,28,56,19,38,13,26,9]),
 (7,[14,5,10,20,7,14,28,56,19,38,13,26,9]),(20,[7,14,5,10,20,7,14,28,56,19,38,13,26,9])]

Notice how the second element of each tuple contains all elements calculated so far. Now you just need to go look for duplicates.

You could, for example, write a function called containsDuplicates with this type:

Prelude> :t containsDuplicates
containsDuplicates :: Eq a => [a] -> Bool

With that, you can use a function like the built-in takeWhile to iterate until you find a duplicate:

Prelude> takeWhile (not . containsDuplicates . snd) $ iterate calcNextAcc (9, [])
[(9,[]),(26,[9]),(13,[26,9]),(38,[13,26,9]),(19,[38,13,26,9]),(56,[19,38,13,26,9]),
 (28,[56,19,38,13,26,9]),(14,[28,56,19,38,13,26,9]),(7,[14,28,56,19,38,13,26,9]),
 (20,[7,14,28,56,19,38,13,26,9]),(10,[20,7,14,28,56,19,38,13,26,9]),
 (5,[10,20,7,14,28,56,19,38,13,26,9]),(14,[5,10,20,7,14,28,56,19,38,13,26,9])]

The last element there contains your solution:

Prelude> last $ takeWhile (not . containsDuplicates . snd) $ iterate calcNextAcc (9, [])
(14,[5,10,20,7,14,28,56,19,38,13,26,9])

You can easily turn that tuple into a list:

Prelude> uncurry (:) $ last $ takeWhile (not . containsDuplicates . snd) $ iterate calcNextAcc (9, [])
[14,5,10,20,7,14,28,56,19,38,13,26,9]

I've left the implementation of the various functions as an exercise.

Sign up to request clarification or add additional context in comments.

Comments

2

threeN consumes a list: xs, starting with a single element in it. It produces a new element: x' based on the value of the head: x of xs; it prepends x' to xs if x' hasn't occurred in xs.

threeN :: [Int] -> [Int]
threeN []          = []
threeN l@(x:xs) 
    | x' `elem` l  = l                      -- base case
    | otherwise    = threeN (x':l)
    where
      x' =  if even x then x `div` 2 else x * 3 - 1

Comments

2

Why the signature is [Integer] -> [Integer]? the input is actually just a number. The following code works.

threeN :: Integer -> [Integer]
threeN n = threeN' n []
  where threeN' n acc 
          | n `elem` acc = n:acc
          | even n = threeN' (n `div` 2) (n:acc)
          | odd n = threeN' (3 * n - 1) (n:acc)

If you are force to use [Integer] as input signature:

threeN :: [Integer] -> [Integer]
threeN [n] = threeN' n []
  where threeN' n acc 
          | n `elem` acc = n:acc
          | even n = threeN' (n `div` 2) (n:acc)
          | odd n = threeN' (3 * n - 1) (n:acc)

But I think It does not make sense.

Regards!

Comments

0

You could use head and tail with elem to test whether the first element already exists in the list. Note however that head and tail are unsafe functions. They will crash if given an empty list.

threeN :: [Integer] -> [Integer]
threeN ns | n `elem` tail ns = ns
          | even n = threeN ([n `div` 2]++ns)
          | odd  n = threeN ([3*n-1]++ns)
  where
    n = head ns

Also if you do not want the repeat number to be in the output, then have the first guard just equal tail ns instead of ns. There is probably a more efficient algorithm to generate these lists, but this just modifies what you've provided.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.