Understanding lists in list in recursive function - haskell

Question

I am writing a function to order a given list by tuples or triples. It should order it by numbers that are between two elements of the list.

for example if given list is [1,2,3,6,7] it should return [[1,2,3], [6,7]] because there is zero numbers between 1,2 and 2,3 and also between 6,7

here is my code:

import Data.List 

check :: [Int] -> [[Int]]
check listCopy@(x:xs) = 
    let sorted = sort (listCopy) 
        in if (length sorted > 1) 
              then if ((sorted !! 1 ) - (sorted !! 0)) == 1 || ((sorted !! 1 ) - (sorted !! 0)) == 0 
                      then [[x]  ++ check(xs) !! 0] 
                      else [[x]] ++ check(xs)
              else [[x]]
check [] = [[]]

if ((sorted !! 1 ) - (sorted !! 0)) == 1 || ((sorted !! 1 ) - (sorted !! 0)) == 0 is checking if there is 0 numbers between two elements of the list

If above statement is True then [[x] ++ check(xs) !! 0] will add that element to the list and call the function again and take the 1st element that it returns. Example: [1,2,3,6,7] -> [[1 ++ check [2,3,6,7]]] -> [[1,2 ++ check[3,6,7]]] and so on...

However when if ((sorted !! 1 ) - (sorted !! 0)) == 1 || ((sorted !! 1 ) - (sorted !! 0)) == 0is False it should else [[x]] ++ check(xs) set the element inside a list inside a list and call function again AND make another new list inside of list. Example: [[1,2 ++ check[3,6,7]]] -> is 6-3 == 0 or 1(False) return [[1,2,3]] + check[6,7] which should result in [[1,2,3], [6,7]]

Calling check[1,2,3,6,7] however returns [[1,2,3]]. I am getting no error, but as I know [[1,2]] ++ [[3,4]] should result in [[1,2], [3,4]] and thats exactly what I am doing in else [[x]] ++ check(xs) and somehow my function ends there. Where did I make mistake or it does something that I am missing?

Answer 1

Well this is an interesting question and here is an experimental approach in applicative style. Yes it looks a little convoluted but in fact very simple. The only thing that i don't like is the usage of last function. May be we can find a way to drop that somehow.

splitConsequtives :: Integral a => [a] -> [[a]]
splitConsequtives xs = foldr id [[last xs]] $ zipWith f <*> tail $ xs
                       where f x y | y-x == 1  = (:) <$> (x:) . head <*> tail
                                   | otherwise = ([x]:)

*Main> splitConsequtives [1,2,3,6,7]
[[1,2,3],[6,7]]
*Main> splitConsequtives [-1,2,3,6,8,9]
[[-1],[2,3],[6],[8,9]]

The idea is to place the constructor functions in a list those will eventually construct our whole result list when chained up by folding. List constructor (:) is right associative and that's why i use foldr.

It all starts with zipWithing our xs list with it's tail by the f function like zipWith f xs (tail xs). The f :: a -> a -> [[a]] -> [[a]] function is where we get our applicatives as elements of the resulting list.

OK..! Now lets focus at the f function which takes x and y as parameters.

• If y is subsequent of x then our [[a]] -> [[a]] type function is (:) <$> (x:) . head <*> tail which takes a list of lists of numbers then takes the sublist at the head, appends x to it and puts everything back together. So if our result being constructed (the accumulator parameter of foldr) is [[7], [9,10]] and x is 6 then we shall get [[6,7],[9,10]].
• If y is not a subsequent of x then our [[a]] -> [[a]] type function is ([x]:). So if our result being constructed (the accumulator parameter of foldr) is [[6,7], [9,10]] and x is 3 then we shall get [[3],[6,7],[9,10]].

One interesting point to notice is the type of iterating function that we use for foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b. You expect it to be of type a -> b -> b but id :: a -> a looks different. How is this possible..? I believe it is because a ~ [[a]] -> [[a]] and b ~ [[a]] in (a -> b -> b) of foldr.

Answer 2

A problem here is that you only append the first sublist:

then [[x]  ++ check(xs) !! 0]

You thus make a recursive call that will return a list of sublists, but you "throw away" all the lists but the first one, and you then concatenate the first one. The remaining sublists, are ignored.

You can fix this with:

then [[x]  ++ check(xs) !! 0] ++ safeTail check

where we implement safeTail as:

safeTail :: [a] -> [a]
safeTail (x:xs) = xs
safeTail [] = []

or, like @melpomene says:

safeTail :: [a] -> [a]
safeTail = drop 1

Later it will turn out we can just use tail, but with the above code, that is difficult to see.

but the implementation is not very "Haskellish". Your code uses a lot of (!!)s, and lengths. Since (!!) runs in O(k) with k the index to of which we want to obtain the element, and length runs in O(n) with n the length of the list, this will also be quite inefficient.

It makes sense to first sort the list before processing it further. Next we only have to look for the current element x, and the next element n, and the rest of the elements xs, so:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:n:xs) = ...
go other = other

In case n <= x+1, then we know that the difference between the two numbers is either zero or one, so in that case the head (first element) of the recursive call to check should be prepended with x, so we can write this like:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:n:xs) | n <= x+1 = (x:r) : rs
            | otherwise = ...
   where (r:rs) = go (n:xs)
go [x] = [[x]]
go [] = []

otherwise we can just construct a singleton list, followed by the rest of the list:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:n:xs) | n <= x+1 = (x:r) : rs
            | otherwise = [x]:(r:rs)
    where (r:rs) = go (n:xs)
go [x] = [[x]]
go [] = []

we know that go (n:xs) has at least one element, since we call the list recursively with one element, and in all cases where the list is non-empty, we return a non-empty list.

By using an as-pattern, we can make this a bit more elegant:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:na@(n:xs)) | n <= x+1 = (x:r) : rs
                 | otherwise = [x]: ra
    where ra@(~(r:rs)) = go na
go [x] = [[x]]
go [] = []

We can generalize the above, like @chepner says, to require only the Eq a, and Ord a:

go :: (Ord n, Enum n) => [n] -> [[n]]
go (x:na@(n:xs)) | succ x >= n = (x:r) : rs
                 | otherwise = [x]: ra
    where ra@(~(r:rs)) = go na
go [x] = [[x]]
go [] = []

So now we only need to express check in terms of go, with:

import Data.List(sort)

check :: (Ord n, Enum n) => [n] -> [[n]]
check = go . sort
    where go (x:na@(n:xs)) | succ x >= n = (x:r) : rs
                           | otherwise = [x]: ra
              where ra@(~(r:rs)) = go na
          go [x] = [[x]]
          go [] = []

or we can let the check function operate on (Eq n, Enum n) types:

import Data.List(sortBy)
import Data.Ord(comparing)

check :: (Ord n, Enum n) => [n] -> [[n]]
check = go . sortBy (comparing fromEnum)
    where go (x:na@(n:xs)) | succ x == n || x == n = (x:r) : rs
                           | otherwise = [x]: ra
              where ra@(~(r:rs)) = go na
          go [x] = [[x]]
          go [] = []