Better Code

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Better Code

Saqib Shamsi
Hi,

The problem that I wish to solve is to divide a (sored) list of integers into sublists such that each sublist contains numbers in consecutive sequence.

For example,
Input: [1,2,3,7,8,10,11,12]
Output: [[1,2,3],[7,8],[10,11,12]]

I have written the following code and it does the trick.

-- Take a list and divide it at first point of non-consecutive number encounter
divide :: [Int] -> [Int] -> ([Int], [Int])
divide first [] = (first, [])
divide first second = if (last first) /= firstSecond - 1 then (first, second)
                      else divide (first ++ [firstSecond]) (tail second)
                      where firstSecond = head second


-- Helper for breaking a list of numbers into consecutive sublists
breakIntoConsecsHelper :: [Int] -> [[Int]] -> [[Int]]
breakIntoConsecsHelper [] [[]] = [[]]
breakIntoConsecsHelper lst ans = if two == [] then ans ++ [one]
                                 else ans ++ [one] ++ breakIntoConsecsHelper two []
                                 where
                                      firstElem = head lst
                                      remaining = tail lst
                                      (one, two) = divide [firstElem] remaining


-- Break the list into sublists of consective numbers
breakIntoConsecs :: [Int] -> [[Int]]
breakIntoConsecs lst = breakIntoConsecsHelper lst [[]]

-- Take the tail of the result given by the function above to get the required list of lists.

However, I was wondering if there was a better way of doing this. Any help would be highly appreciated.

Thank you.
Best Regards,
Saqib Shamsi

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Francesco Ariis
On Fri, Jan 13, 2017 at 09:35:54PM +0530, Saqib Shamsi wrote:

> The problem that I wish to solve is to divide a (sored) list of integers
> into sublists such that each sublist contains numbers in consecutive
> sequence.
>
> For example,
> *Input:* [1,2,3,7,8,10,11,12]
> *Output:* [[1,2,3],[7,8],[10,11,12]]
>
> [...]
>
> However, I was wondering if there was a better way of doing this. Any help
> would be highly appreciated.

Hello Saquib,
    you could try using a 'trick' like this:

λ> zipWith (-) [1,2,3,7,8,10,11,12] (enumFrom 1)
[0,0,0,3,3,4,4,4]

Now you have an 'helper' list which can be glued to the first one
with zip

λ> zip [1,2,3,7,8,10,11,12] it
[(1,0),(2,0),(3,0),(7,3),(8,3),(10,4),(11,4),(12,4)]

and now grouped by using `groupBy` in Data.List.

Does that help?
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Joel Neely
The "helper list" technique is ingenious, but seems very specific to Int as the type within the list.

I have had other tasks that seem to fit a more generalized problem statement, of which the original question appears to me as special case:

Given a criterion of type a -> a -> Bool and a list [a], produce a list of lists [[a]] in which sub-lists are made up of consecutive elements from the original list that satisfy the criterion.

It appears to me that List.groupBy may meet that need, but I'm not able to verify that at the moment (and would be glad of feedback).

-jn-





On Fri, Jan 13, 2017 at 10:55 AM, Francesco Ariis <[hidden email]> wrote:
On Fri, Jan 13, 2017 at 09:35:54PM +0530, Saqib Shamsi wrote:
> The problem that I wish to solve is to divide a (sored) list of integers
> into sublists such that each sublist contains numbers in consecutive
> sequence.
>
> For example,
> *Input:* [1,2,3,7,8,10,11,12]
> *Output:* [[1,2,3],[7,8],[10,11,12]]
>
> [...]
>
> However, I was wondering if there was a better way of doing this. Any help
> would be highly appreciated.

Hello Saquib,
    you could try using a 'trick' like this:

λ> zipWith (-) [1,2,3,7,8,10,11,12] (enumFrom 1)
[0,0,0,3,3,4,4,4]

Now you have an 'helper' list which can be glued to the first one
with zip

λ> zip [1,2,3,7,8,10,11,12] it
[(1,0),(2,0),(3,0),(7,3),(8,3),(10,4),(11,4),(12,4)]

and now grouped by using `groupBy` in Data.List.

Does that help?
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



--
Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Joel Neely
In reply to this post by Saqib Shamsi
Had a chance to chat with ghci, so earlier conjecture not confirmed:

Prelude Data.List> groupBy (\x y -> x == y-1) [1,2,3,7,8,10,11,12]

[[1,2],[3],[7,8],[10,11],[12]]

So close but no cigar.


On Fri, Jan 13, 2017 at 10:05 AM, Saqib Shamsi <[hidden email]> wrote:
Hi,

The problem that I wish to solve is to divide a (sored) list of integers into sublists such that each sublist contains numbers in consecutive sequence.

For example,
Input: [1,2,3,7,8,10,11,12]
Output: [[1,2,3],[7,8],[10,11,12]]

I have written the following code and it does the trick.

-- Take a list and divide it at first point of non-consecutive number encounter
divide :: [Int] -> [Int] -> ([Int], [Int])
divide first [] = (first, [])
divide first second = if (last first) /= firstSecond - 1 then (first, second)
                      else divide (first ++ [firstSecond]) (tail second)
                      where firstSecond = head second


-- Helper for breaking a list of numbers into consecutive sublists
breakIntoConsecsHelper :: [Int] -> [[Int]] -> [[Int]]
breakIntoConsecsHelper [] [[]] = [[]]
breakIntoConsecsHelper lst ans = if two == [] then ans ++ [one]
                                 else ans ++ [one] ++ breakIntoConsecsHelper two []
                                 where
                                      firstElem = head lst
                                      remaining = tail lst
                                      (one, two) = divide [firstElem] remaining


-- Break the list into sublists of consective numbers
breakIntoConsecs :: [Int] -> [[Int]]
breakIntoConsecs lst = breakIntoConsecsHelper lst [[]]

-- Take the tail of the result given by the function above to get the required list of lists.

However, I was wondering if there was a better way of doing this. Any help would be highly appreciated.

Thank you.
Best Regards,
Saqib Shamsi

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners




--
Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Carlo Matteo Scalzo
In reply to this post by Saqib Shamsi
Hi Saqib,

perhaps something like this?


divide :: [Int] -> [[Int]]                                                                                                                                    

divide []     = []                                                                                                                                            

divide (x:xs) = divideAux xs [] [x] x                                                                                                                         

                                                                                                                                                              

divideAux :: [Int] -> [[Int]] -> [Int] -> Int -> [[Int]]                                                                                                      

divideAux [] result current max        = result ++ [current]                                                                                                     

divideAux (x:xs) result current max = if x - max > 1                                                                                                          

                                                              then divideAux xs (result ++ [current]) [x] x                                                                        

                                                              else divideAux xs result (current ++ [x]) x



This can of course be generalised to other types (as per Joel's requirement) just by replacing the check on line 7, i.e., 'x - max > 1'.

Happy to explain/talk about the code if you'd like me to :-)

Cheers,

Carlo

On Fri, Jan 13, 2017 at 7:14 PM, Joel Neely <[hidden email]> wrote:
Had a chance to chat with ghci, so earlier conjecture not confirmed:

Prelude Data.List> groupBy (\x y -> x == y-1) [1,2,3,7,8,10,11,12]

[[1,2],[3],[7,8],[10,11],[12]]

So close but no cigar.


On Fri, Jan 13, 2017 at 10:05 AM, Saqib Shamsi <[hidden email]> wrote:
Hi,

The problem that I wish to solve is to divide a (sored) list of integers into sublists such that each sublist contains numbers in consecutive sequence.

For example,
Input: [1,2,3,7,8,10,11,12]
Output: [[1,2,3],[7,8],[10,11,12]]

I have written the following code and it does the trick.

-- Take a list and divide it at first point of non-consecutive number encounter
divide :: [Int] -> [Int] -> ([Int], [Int])
divide first [] = (first, [])
divide first second = if (last first) /= firstSecond - 1 then (first, second)
                      else divide (first ++ [firstSecond]) (tail second)
                      where firstSecond = head second


-- Helper for breaking a list of numbers into consecutive sublists
breakIntoConsecsHelper :: [Int] -> [[Int]] -> [[Int]]
breakIntoConsecsHelper [] [[]] = [[]]
breakIntoConsecsHelper lst ans = if two == [] then ans ++ [one]
                                 else ans ++ [one] ++ breakIntoConsecsHelper two []
                                 where
                                      firstElem = head lst
                                      remaining = tail lst
                                      (one, two) = divide [firstElem] remaining


-- Break the list into sublists of consective numbers
breakIntoConsecs :: [Int] -> [[Int]]
breakIntoConsecs lst = breakIntoConsecsHelper lst [[]]

-- Take the tail of the result given by the function above to get the required list of lists.

However, I was wondering if there was a better way of doing this. Any help would be highly appreciated.

Thank you.
Best Regards,
Saqib Shamsi

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners




--
Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners




--
Carlo Matteo Scalzo

Mobile: +44 (0) 7934 583582

E-mail: [hidden email]

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Graham Gill
In reply to this post by Saqib Shamsi
Here's one that does what you want, doesn't require the list to be sorted, and groups together consecutive and equal terms:

groupConsecutive :: (Enum a,Eq a) => [a] -> [[a]]
groupConsecutive = foldr go []
    where go x ls@(hd@(y:_):yss)
            | x == y || x == pred y = (x:hd):yss
            | otherwise             = [x]:ls
          go x [] = [[x]]
          go x ([]:yss) = [x]:yss

Then
> groupConsecutive [1,2,3,7,8,10,11,12]
[[1,2,3],[7,8],[10,11,12]]

> groupConsecutive [1,2,2,3,2,3]
[[1,2,2,3],[2,3]]

and
> groupConsecutive "bookkeeper understudy"
["b","oo","kk","ee","p","e","r"," ","u","n","de","rstu","d","y"]

The third case of go will never be reached. If you use a type that is also an instance of Bounded, and if your list contains the minimum element of the type, you'll get a runtime error on the use of pred. For example:

> groupConsecutive [True,False,True]
*** Exception: Prelude.Enum.Bool.pred: bad argument

Graham

On 13-Jan-2017 11:05 AM, Saqib Shamsi wrote:
Hi,

The problem that I wish to solve is to divide a (sored) list of integers into sublists such that each sublist contains numbers in consecutive sequence.

For example,
Input: [1,2,3,7,8,10,11,12]
Output: [[1,2,3],[7,8],[10,11,12]]

I have written the following code and it does the trick.

-- Take a list and divide it at first point of non-consecutive number encounter
divide :: [Int] -> [Int] -> ([Int], [Int])
divide first [] = (first, [])
divide first second = if (last first) /= firstSecond - 1 then (first, second)
                      else divide (first ++ [firstSecond]) (tail second)
                      where firstSecond = head second


-- Helper for breaking a list of numbers into consecutive sublists
breakIntoConsecsHelper :: [Int] -> [[Int]] -> [[Int]]
breakIntoConsecsHelper [] [[]] = [[]]
breakIntoConsecsHelper lst ans = if two == [] then ans ++ [one]
                                 else ans ++ [one] ++ breakIntoConsecsHelper two []
                                 where
                                      firstElem = head lst
                                      remaining = tail lst
                                      (one, two) = divide [firstElem] remaining


-- Break the list into sublists of consective numbers
breakIntoConsecs :: [Int] -> [[Int]]
breakIntoConsecs lst = breakIntoConsecsHelper lst [[]]

-- Take the tail of the result given by the function above to get the required list of lists.

However, I was wondering if there was a better way of doing this. Any help would be highly appreciated.

Thank you.
Best Regards,
Saqib Shamsi


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Graham Gill
Sorry, I mean, "groups together consecutive and equal terms, that occur
sequentially". Examples speak louder than general descriptions!

On 13-Jan-2017 6:43 PM, Graham Gill wrote:
> Here's one that does what you want, doesn't require the list to be
> sorted, and groups together consecutive and equal terms:


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Better Code

Jeffrey Brown
You could zip the original list to its own tail.


On Fri, Jan 13, 2017 at 4:09 PM, Graham Gill <[hidden email]> wrote:
Sorry, I mean, "groups together consecutive and equal terms, that occur sequentially". Examples speak louder than general descriptions!

On 13-Jan-2017 6:43 PM, Graham Gill wrote:
Here's one that does what you want, doesn't require the list to be sorted, and groups together consecutive and equal terms:


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



--
Jeff Brown | Jeffrey Benjamin Brown
Website   |   Facebook   |   LinkedIn(spammy, so I often miss messages here)   |   Github   

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners