Reversing a list

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Reversing a list

Jona Ekenberg
Hello,

I'm currently going through the exercises in chapter 3 of Real World Haskell. One of the exercises challenges me to create a function which takes a list and makes a palindrome of it.

I tried to solve it this way:
palindrome :: [t] -> [t]
palindrome xs = xs ++ (reverse xs)
  where
    reverse []     = []
    reverse (x:xs) = (reverse xs) ++ x

But when I try to compile this I get this error:
Kapitel3.hs:14:32-33: error: …
    • Couldn't match type ‘t’ with ‘[t]’
      ‘t’ is a rigid type variable bound by
        the type signature for:
          palindrome :: forall t. [t] -> [t]
        at /Users/jona/programmering/haskell/boken/Kapitel3.hs:13:15
      Expected type: [[t]]
        Actual type: [t]
    • In the first argument of ‘reverse’, namely ‘xs’
      In the second argument of ‘(++)’, namely ‘(reverse xs)’
      In the expression: xs ++ (reverse xs)
    • Relevant bindings include
        xs :: [t]
          (bound at /Users/jona/programmering/haskell/boken/Kapitel3.hs:14:12)
        palindrome :: [t] -> [t]
          (bound at /Users/jona/programmering/haskell/boken/Kapitel3.hs:14:1)
Compilation failed.

It looks like I have used a function that want a list of lists, but I don't understand where.
Also, is there some way to declare the type of my reverse-function in this case?

Kind regards,
Jona Ekenberg

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

Re: Reversing a list

Frederic Cogny
Looks like you're missing the square brackets around your x in the definition of reverse (the ++ takes two lists, hence the error message)

Try this
 
palindrome :: [t] -> [t]
palindrome xs = xs ++ (reverse xs)
  where
    reverse []     = []
    reverse (x:xs) = (reverse xs) ++ [x]


to declare the type you can define it outside or annotate it within you're code

palindrome :: [t] -> [t]
palindrome xs = xs ++ (reverse xs)
  where
    reverse :: [t] -> [t]
    reverse []     = []
    reverse (x:xs) = (reverse xs) ++ [x]

On Tue, Jul 4, 2017 at 12:07 PM Jona Ekenberg <[hidden email]> wrote:
Hello,

I'm currently going through the exercises in chapter 3 of Real World Haskell. One of the exercises challenges me to create a function which takes a list and makes a palindrome of it.

I tried to solve it this way:
palindrome :: [t] -> [t]
palindrome xs = xs ++ (reverse xs)
  where
    reverse []     = []
    reverse (x:xs) = (reverse xs) ++ x

But when I try to compile this I get this error:
Kapitel3.hs:14:32-33: error: …
    • Couldn't match type ‘t’ with ‘[t]’
      ‘t’ is a rigid type variable bound by
        the type signature for:
          palindrome :: forall t. [t] -> [t]
        at /Users/jona/programmering/haskell/boken/Kapitel3.hs:13:15
      Expected type: [[t]]
        Actual type: [t]
    • In the first argument of ‘reverse’, namely ‘xs’
      In the second argument of ‘(++)’, namely ‘(reverse xs)’
      In the expression: xs ++ (reverse xs)
    • Relevant bindings include
        xs :: [t]
          (bound at /Users/jona/programmering/haskell/boken/Kapitel3.hs:14:12)
        palindrome :: [t] -> [t]
          (bound at /Users/jona/programmering/haskell/boken/Kapitel3.hs:14:1)
Compilation failed.

It looks like I have used a function that want a list of lists, but I don't understand where.
Also, is there some way to declare the type of my reverse-function in this case?

Kind regards,
Jona Ekenberg
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
Frederic Cogny
+33 7 83 12 61 69

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

Re: Reversing a list

Francesco Ariis
In reply to this post by Jona Ekenberg
On Tue, Jul 04, 2017 at 12:06:39PM +0200, Jona Ekenberg wrote:

> Hello,
>
> I'm currently going through the exercises in chapter 3 of Real World
> Haskell. One of the exercises challenges me to create a function which
> takes a list and makes a palindrome of it.
>
> I tried to solve it this way:
> palindrome :: [t] -> [t]
> palindrome xs = xs ++ (reverse xs)
>   where
>     reverse []     = []
>     reverse (x:xs) = (reverse xs) ++ x

Hello Jona,

    let's analyse the error.
It points to this bit:

    palindrome xs = xs ++ (reverse xs)

And it says: I expected [[t]], but you gave me [t]. Whenever I encounter
such an error I try to write explicit type signatures so to make diagnosing
easier. In your example

    palindrome :: [t] -> [t]
    palindrome xs = xs ++ (reverse xs)
      where
          reverse :: [t] -> [t] -- explicit type signature
          reverse []     = []
          reverse (x:xs) = (reverse xs) ++ x

If we :reload ghci complains again, the offending bit being

    reverse (x:xs) = (reverse xs) ++ x
                                     ^
Expected type is [t1] but we passed t. Not it is clear! The type of `++` is:

    λ> :t (++)
    (++) :: [a] -> [a] -> [a]

and `x` is a single element. When we replace `x` with `[x]` everything works.

Does that help?
-F

P.S.: Real World Haskell is an excellent book but sometimes can be a tad
difficult to follow. If you want to integrate with another source, CIS194 [1]
is an excellent choice: free, thorough, full of home-works and interactive.

[1] http://www.cis.upenn.edu/~cis194/fall16/

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

Re: Reversing a list

Jona Ekenberg
Thank you both for your answers, I somehow thought ++ acted as both append and concat, since I've mostly used it on strings where I haven't had to think about it.

And thank you for the tips regarding adding explicit types and the reading material. So far I feel that I'm able to follow along quite well, but it's nice to have a second source!

Grateful regards,
Jona

Den 4 juli 2017 12:21 em skrev "Francesco Ariis" <[hidden email]>:
On Tue, Jul 04, 2017 at 12:06:39PM +0200, Jona Ekenberg wrote:
> Hello,
>
> I'm currently going through the exercises in chapter 3 of Real World
> Haskell. One of the exercises challenges me to create a function which
> takes a list and makes a palindrome of it.
>
> I tried to solve it this way:
> palindrome :: [t] -> [t]
> palindrome xs = xs ++ (reverse xs)
>   where
>     reverse []     = []
>     reverse (x:xs) = (reverse xs) ++ x

Hello Jona,

    let's analyse the error.
It points to this bit:

    palindrome xs = xs ++ (reverse xs)

And it says: I expected [[t]], but you gave me [t]. Whenever I encounter
such an error I try to write explicit type signatures so to make diagnosing
easier. In your example

    palindrome :: [t] -> [t]
    palindrome xs = xs ++ (reverse xs)
      where
          reverse :: [t] -> [t] -- explicit type signature
          reverse []     = []
          reverse (x:xs) = (reverse xs) ++ x

If we :reload ghci complains again, the offending bit being

    reverse (x:xs) = (reverse xs) ++ x
                                     ^
Expected type is [t1] but we passed t. Not it is clear! The type of `++` is:

    λ> :t (++)
    (++) :: [a] -> [a] -> [a]

and `x` is a single element. When we replace `x` with `[x]` everything works.

Does that help?
-F

P.S.: Real World Haskell is an excellent book but sometimes can be a tad
difficult to follow. If you want to integrate with another source, CIS194 [1]
is an excellent choice: free, thorough, full of home-works and interactive.

[1] http://www.cis.upenn.edu/~cis194/fall16/

_______________________________________________
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
|  
Report Content as Inappropriate

Re: Reversing a list

Frerich Raabe
In reply to this post by Jona Ekenberg
On 2017-07-04 12:06, Jona Ekenberg wrote:

> Hello,
>
> I'm currently going through the exercises in chapter 3 of Real World
> Haskell. One of the exercises challenges me to create a function which
> takes a list and makes a palindrome of it.
>
> I tried to solve it this way:
>
> palindrome :: [t] -> [t]
> palindrome xs = xs ++ (reverse xs)
>   where
>     reverse []     = []
>     reverse (x:xs) = (reverse xs) ++ x
>
> But when I try to compile this I get this error:

[..]

This is caused by Haskell trying hard to make your code type check but the
noticing that it just cannot make the parts fit together.

I suspect the cause of this is the definition

   reverse (x:xs) = (reverse xs) ++ x

What's noteworthy about this is:

   1. The type of the ':' constructor you used in the pattern match is 'a ->
[a] -> [a]', i.e. the first argument is of some type 'a' (in Haskell
nomenclature, 'x :: a') and the second argument is a list (i.e. 'xs :: [a]').
So your compiler knows that no matter what type 'x' is, 'xs' will be a list
of those things.

   2. The type of the '++' function you used on the right-hand side is '[a] ->
[a] -> [a]', i.e. the first and the second argument must be of the same type
(a list of things). Since the second argument must be a list, this means that
'x' must be a list and hence (considering 1. above) 'xs' must be a list of
lists.

This means that your 'reverse' definition must be of type '[[a]] -> [a]': it
takes a list of list of things and yields a list of things. I.e. it takes and
returns different type sof things.

This however is in conflict with your first definition:

   palindrome xs = xs ⧺ (reverse xs)

For 'xs ⧺ (reverse xs)' to be sound (to 'type-check'), the expressions 'xs'
and '(reverse xs)' have to be of the same type. And since 'xs' is also an
argument to 'reverse' it means that 'reverse' has to take and yield values of
the same type.

You can resolve this conflict by changing

   reverse (x:xs) = (reverse xs) ++ x

to

   reverse (x:xs) = (reverse xs) ++ [x]

--
Frerich Raabe - [hidden email]
www.froglogic.com - Multi-Platform GUI Testing
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Loading...