merge error

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

merge error

trent shipley

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys



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

Re: merge error

Alex Rozenshteyn
If you compile with -Wall, you get the following

foo.hs:2:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘merge’:
        Patterns not matched:
            [] (_:_:_)
            (_:_:_) []
  |
2 | merge [] [] = []
  | ^^^^^^^^^^^^^^^^...

That is to say, you never match if there is an empty list and a list of 2 or more.

Try this:

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second
                                 | otherwise  = y : merge first ys


On Thu, May 17, 2018 at 10:21 PM trent shipley <[hidden email]> wrote:

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys


_______________________________________________
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: merge error

mukesh tiwari
In reply to this post by trent shipley
I have changed your code little bit, and now it works.

merge :: Ord a => [a] -> [a] -> [a]
merge [] second = second
merge first [] = first
merge first@(x:xs) second@(y:ys)
  | x <= y    = x : merge xs second
  | otherwise = y : merge first ys

The reason your code is not working because
merge [4,5] [] is trying to match it against merge [x] [] = [x] which expects one element list at first place so merge [1] [] would work,but not merge (list having more than one element) [].

Best,
Mukesh Tiwari



On Fri, May 18, 2018 at 3:20 PM, trent shipley <[hidden email]> wrote:

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys



_______________________________________________
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: merge error

Hemanth Gunda
In reply to this post by trent shipley
Hi Trent, 

This works: 

merge:: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge x [] = x
merge [] y = y
merge first@(x:xs) second@(y:ys)
| x <= y = x : merge xs second
| otherwise = y : merge first ys

Difference in the lines

merge x [] = x
merge [] y = y

As the input is of type [a] where a belongs to typeclass Ord, you must pass x instead of [x]. 

[x] would work if you tried merge [4] []. but will fail if you tried merge [4,5] []. because "4,5" isn't of type a. 

Regards, Hemanth


On Fri, May 18, 2018 at 10:51 AM trent shipley <[hidden email]> wrote:

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys


_______________________________________________
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: merge error

trent shipley
Thanks to all. I used Mukesh's suggestion. 

I am still not clear on:

why [x] /= xs
why first == first@(x:xs), especially weather the variable declarations are considered names for the same thing.

On Thu, May 17, 2018 at 10:39 PM Hemanth Gunda <[hidden email]> wrote:
Hi Trent, 

This works: 

merge:: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge x [] = x
merge [] y = y
merge first@(x:xs) second@(y:ys)
| x <= y = x : merge xs second
| otherwise = y : merge first ys

Difference in the lines

merge x [] = x
merge [] y = y

As the input is of type [a] where a belongs to typeclass Ord, you must pass x instead of [x]. 

[x] would work if you tried merge [4] []. but will fail if you tried merge [4,5] []. because "4,5" isn't of type a. 

Regards, Hemanth


On Fri, May 18, 2018 at 10:51 AM trent shipley <[hidden email]> wrote:

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys


_______________________________________________
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

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

Re: merge error

Ut Primum
[x] means a list containing the element x

xs in general is only a variable named xs, and in particular could be a list; in this case, if you write
first@(x:xs)
you mean that first is a list, its "head" is x and xs is its "tail", i.e. all the elements of the list first following x.

For example if the arguments of merge are [1,2,4] and [3,6], then
first = [1,2,4]
x=1
xs = [2,4]
second=[3,6]
y=3
ys=[6]

Note that [1,2,4] could not be pattern-matchd with [x]. [6] could (because contains just one element)

Il ven 18 mag 2018, 08:04 trent shipley <[hidden email]> ha scritto:
Thanks to all. I used Mukesh's suggestion. 

I am still not clear on:

why [x] /= xs
why first == first@(x:xs), especially weather the variable declarations are considered names for the same thing.

On Thu, May 17, 2018 at 10:39 PM Hemanth Gunda <[hidden email]> wrote:
Hi Trent, 

This works: 

merge:: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge x [] = x
merge [] y = y
merge first@(x:xs) second@(y:ys)
| x <= y = x : merge xs second
| otherwise = y : merge first ys

Difference in the lines

merge x [] = x
merge [] y = y

As the input is of type [a] where a belongs to typeclass Ord, you must pass x instead of [x]. 

[x] would work if you tried merge [4] []. but will fail if you tried merge [4,5] []. because "4,5" isn't of type a. 

Regards, Hemanth


On Fri, May 18, 2018 at 10:51 AM trent shipley <[hidden email]> wrote:

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys


_______________________________________________
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
_______________________________________________
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: merge error

Hemanth Gunda
In reply to this post by trent shipley
Hi Trent, 

why first == first@(x:xs), especially weather the variable declarations are considered names for the same thing.

first@(x:xs) is meant to be read as below:

"first as (x:xs)". 

This is syntactic sugar that gives you the flexibility to address the entire list as "first", the first element (head) of the list as "x" and the rest of the list (tail) as xs. 

If you don't want to use @, you can write the last case in your program as: 

merge first second | (head first) <= (head second)     = (head first) : merge (tail first) second

                   | otherwise  = (head second): merge first (tail second) 


instead of 

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys



why [x] /= xs

when you call merge as: 

> merge first second

from merge type signature,

merge :: Ord a => [a] -> [a] -> [a]

 we know it takes  two lists of type a, belonging to typeclass Ord (where <, >  has meaning)

first & second checked for being a list & whatever is present inside the list is expected to be of typeclass Ord. 

Case A: If you wrote merge [x] [] = [x] 

[x] is expected to be a list of Ord
which means x is expected to be Ord. 

Case B: if you called merge x [] = x

x is expected to be a list of Ord.

When you call merge [4,5] []

In Case A, it implies "4,5" is a member of Ord, as this is x. Which it isn't (as 3 <"4,5" has no meaning). Therefore merge [x] [] = [x] isn't executed here, the program goes looking for other cases & doesn't find any that satisfies these input types & leads to the error you encountered. 

In Case B, it imples [4,5] is a list of Ords, which corresponds to the correct type. Therefore this statement is executed. 

Regards, Hemanth


On Fri, May 18, 2018 at 11:34 AM trent shipley <[hidden email]> wrote:
Thanks to all. I used Mukesh's suggestion. 

I am still not clear on:

why [x] /= xs
why first == first@(x:xs), especially weather the variable declarations are considered names for the same thing.

On Thu, May 17, 2018 at 10:39 PM Hemanth Gunda <[hidden email]> wrote:
Hi Trent, 

This works: 

merge:: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge x [] = x
merge [] y = y
merge first@(x:xs) second@(y:ys)
| x <= y = x : merge xs second
| otherwise = y : merge first ys

Difference in the lines

merge x [] = x
merge [] y = y

As the input is of type [a] where a belongs to typeclass Ord, you must pass x instead of [x]. 

[x] would work if you tried merge [4] []. but will fail if you tried merge [4,5] []. because "4,5" isn't of type a. 

Regards, Hemanth


On Fri, May 18, 2018 at 10:51 AM trent shipley <[hidden email]> wrote:

The below produces an error. And I am very proud that I could use the GHCi debugging tools to get this far.

merge [] [] works.

merge [1] [] works.

I don't know why the failing example fails. It should return:

[4,5]

Help to unstuck is appreciated.

:step merge [4,5] []

*** Exception: ex6_8.hs:(12,1)-(16,66): Non-exhaustive patterns in function merge

Given:

merge :: Ord a => [a] -> [a] -> [a]

merge [] [] = []

merge [x] [] = [x]

merge [] [y] = [y]

merge first@(x:xs) second@(y:ys) | x <= y     = x : merge xs second

                                 | otherwise  = y : merge first ys


_______________________________________________
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
_______________________________________________
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