Defeating type inference

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

Defeating type inference

Philip Scott
Well, either that or I being an idiot.

Here's a little example. Let us say you had a datatype 'Month'*

data Month = Jan
       |     Feb
       |     Mar
       |     Apr
       |     May
       |     Jun
       |     Jul
       |     Aug
       |     Sep
       |     Oct
       |     Nov
       |     Dec
       deriving(Show, Eq, Ord, Ix)

What I would like to make is an infinite lazy list of months (called,
rather imaginitively I thought, 'months') that keeps wrapping around.
That is to say, it would make a list like this

[Jan, Feb, ...., Nov, Dec, Jan, Feb, ....., Nov, Dec, ... ad infinitum ]

I am sure you get the picture. My first stab was this:

months = range (Jan, Dec) : months

But of course, what you get here is a list of lists, with each element
being a list of [Jan, Feb, ...., Dec]

So I puzzled for a little bit about how to do this in the most Haskelly
way and I thought of this

months = concat (range (Jan, Dec) : months)

Which should work, right**

But the type checker is not pleased at all and complains:

        Couldn't match expected type `[Month]'
               against inferred type `Month'
          Expected type: [[Month]]
          Inferred type: [Month]
        In the expression: concat (range (Jan, Dec) : months)
        In the definition of `months':
            months = concat (range (Jan, Dec) : months)

However, if you use the first definition and make a second function:

months = range (Jan, Dec) : months
realmonths = concat(months)

It is happy and does what one might expect. I thought perhaps I was just
confusing the inference engine so I tried a liberal sprinkling of ::
operators to make my intentions clear, but it still wasn't having any of it.

Any thoughts welcomed!

- Philip

* I am aware that there is plenty of code to handle dates and times
already written, probably much more nicely than mine - this is just a
project I have been hacking at to get to grips with things.
** though I am pretty sure this is the Wrong Way to do this. I suspect
concat takes O(n) time - more elegant approaches would be welcomed!

Reply | Threaded
Open this post in threaded view
|

Defeating type inference

Antoine Latter-2
On Wed, Feb 25, 2009 at 6:18 PM, Philip Scott <[hidden email]> wrote:

> Well, either that or I being an idiot.
>
> Here's a little example. Let us say you had a datatype 'Month'*
>
> data Month = Jan
> ? ? ?| ? ? Feb
> ? ? ?| ? ? Mar
> ? ? ?| ? ? Apr
> ? ? ?| ? ? May
> ? ? ?| ? ? Jun
> ? ? ?| ? ? Jul
> ? ? ?| ? ? Aug
> ? ? ?| ? ? Sep
> ? ? ?| ? ? Oct
> ? ? ?| ? ? Nov
> ? ? ?| ? ? Dec
> ? ? ?deriving(Show, Eq, Ord, Ix)
<SNIP>

> months = concat (range (Jan, Dec) : months)
>
> Which should work, right**
>
> But the type checker is not pleased at all and complains:
>
> ? ? ? Couldn't match expected type `[Month]'
> ? ? ? ? ? ? ?against inferred type `Month'
> ? ? ? ? Expected type: [[Month]]
> ? ? ? ? Inferred type: [Month]
> ? ? ? In the expression: concat (range (Jan, Dec) : months)
> ? ? ? In the definition of `months':
> ? ? ? ? ? months = concat (range (Jan, Dec) : months)
>
> However, if you use the first definition and make a second function:
>
> months = range (Jan, Dec) : months
> realmonths = concat(months)
>
> It is happy and does what one might expect. I thought perhaps I was just
> confusing the inference engine so I tried a liberal sprinkling of ::
> operators to make my intentions clear, but it still wasn't having any of it.
>

Can you post your version of the problem function which includes type
signatures?  Can you also write-out a top-level type signature for the
entire expression?

Antoine
Reply | Threaded
Open this post in threaded view
|

Defeating type inference

Alexander Dunlap
In reply to this post by Philip Scott
On Wed, Feb 25, 2009 at 4:18 PM, Philip Scott <[hidden email]> wrote:

> months = range (Jan, Dec) : months
>
> But of course, what you get here is a list of lists, with each element being
> a list of [Jan, Feb, ...., Dec]
>
> So I puzzled for a little bit about how to do this in the most Haskelly way
> and I thought of this
>
> months = concat (range (Jan, Dec) : months)
>
> Which should work, right**
>
> But the type checker is not pleased at all and complains:
>
> ? ? ? Couldn't match expected type `[Month]'
> ? ? ? ? ? ? ?against inferred type `Month'
> ? ? ? ? Expected type: [[Month]]
> ? ? ? ? Inferred type: [Month]
> ? ? ? In the expression: concat (range (Jan, Dec) : months)
> ? ? ? In the definition of `months':
> ? ? ? ? ? months = concat (range (Jan, Dec) : months)
>
> However, if you use the first definition and make a second function:
>
> months = range (Jan, Dec) : months
> realmonths = concat(months)
>

The problem is that when you go from

> months = range (Jan,Dec) : months
> realmonths = concat months

to

> months = concat (range (Jan,Dec) : months)

you're not just collapsing the two functions, you're changing the
definition (and type!) of "months" which you referred to within the
months function. Since months is a recursive function, you can't
necessary fold in the definition of realmonths because you want the
recursion to apply to the original months, not the original
realmonths.

As you suspected, there are better and simpler ways of doing this
available, although your way is good for getting the hang of
recursion, even though experienced haskellers really don't use
recursion all that much. (Most prefer to use functions that
encapsulate recursion *patterns* such as map, filter, folds and many
more.) You could use list concatentation while keeping the recursion,
as in

> months = range (Jan,Dec) ++ months

Even better, import Data.List and use the built-in cycle function
(http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-List.html#v%3Acycle):

> months = cycle (range (Jan,Dec))

Hope that helps.

Alex
Reply | Threaded
Open this post in threaded view
|

Defeating type inference

Daniel Fischer-4
Am Donnerstag, 26. Februar 2009 06:05 schrieb Alexander Dunlap:

> On Wed, Feb 25, 2009 at 4:18 PM, Philip Scott <[hidden email]> wrote:
> > months = range (Jan, Dec) : months
> >
> > But of course, what you get here is a list of lists, with each element
> > being a list of [Jan, Feb, ...., Dec]
> >
> > So I puzzled for a little bit about how to do this in the most Haskelly
> > way and I thought of this
> >
> > months = concat (range (Jan, Dec) : months)
> >
> > Which should work, right**
> >
> > But the type checker is not pleased at all and complains:
> >
> >       Couldn't match expected type `[Month]'
> >              against inferred type `Month'
> >         Expected type: [[Month]]
> >         Inferred type: [Month]
> >       In the expression: concat (range (Jan, Dec) : months)
> >       In the definition of `months':
> >           months = concat (range (Jan, Dec) : months)
> >
> > However, if you use the first definition and make a second function:
> >
> > months = range (Jan, Dec) : months
> > realmonths = concat(months)
>
> The problem is that when you go from
>
> > months = range (Jan,Dec) : months
> > realmonths = concat months
>
> to
>
> > months = concat (range (Jan,Dec) : months)
>
> you're not just collapsing the two functions, you're changing the
> definition (and type!) of "months" which you referred to within the
> months function. Since months is a recursive function, you can't
> necessary fold in the definition of realmonths because you want the
> recursion to apply to the original months, not the original
> realmonths.
>
> As you suspected, there are better and simpler ways of doing this
> available, although your way is good for getting the hang of
> recursion, even though experienced haskellers really don't use
> recursion all that much. (Most prefer to use functions that
> encapsulate recursion *patterns* such as map, filter, folds and many
> more.) You could use list concatentation while keeping the recursion,
> as in
>
> > months = range (Jan,Dec) ++ months
>
> Even better, import Data.List and use the built-in cycle function
>
>
(http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-List.html#v%3Acycle):
> > months = cycle (range (Jan,Dec))

One more improvement, include also Enum among the derived classes, then you
can write

months = cycle [Jan .. Dec]

Oh, and cycle is also exported from the Prelude, so it's not necessary to
import Data.List for that (though you will probably want to imoprt it
anyway).


>
> Hope that helps.
>
> Alex

Cheers,
Daniel

Reply | Threaded
Open this post in threaded view
|

Defeating type inference

Philip Scott
In reply to this post by Alexander Dunlap
Hi Alex,

> The problem is that when you go fro
>> months = range (Jan,Dec) : months
>> realmonths = concat months
>>    
> to
>> months = concat (range (Jan,Dec) : months)
>>    
> you're not just collapsing the two functions, you're changing the
> definition (and type!) of "months" which you referred to within the
> months function. Since months is a recursive function, you can't
> necessary fold in the definition of realmonths because you want the
> recursion to apply to the original months, not the original
> realmonths.
>
>  
Of course, why didn't I see that :) I think I had managed to get my head
into its own recursive loop.. I think I might have to replace my evening
glass or three of wine with some Red Bull while I am getting my mind
around this stuff.
> As you suspected, there are better and simpler ways of doing this
> available, although your way is good for getting the hang of
> recursion, even though experienced haskellers really don't use
> recursion all that much. (Most prefer to use functions that
> encapsulate recursion *patterns* such as map, filter, folds and many
> more.)
>  
Thank you very much for you help and suggestions, I shall bear them in mind.

- Philip
Reply | Threaded
Open this post in threaded view
|

Defeating type inference

Philip Scott
In reply to this post by Daniel Fischer-4
Hi ho,
> One more improvement, include also Enum among the derived classes, then you
> can write
>
> months = cycle [Jan .. Dec]
>
> Oh, and cycle is also exported from the Prelude, so it's not necessary to
> import Data.List for that (though you will probably want to imoprt it
> anyway).
>  

Ohh so many little tasty titbits of Haskell - I was trying for ages to
get the '..' operator to work. I guess I will start to know where to
look for these guys as time goes on.

Cheers,

Philip
Reply | Threaded
Open this post in threaded view
|

Defeating type inference

Daniel Fischer-4
Am Donnerstag, 26. Februar 2009 12:26 schrieb Philip Scott:

> Hi ho,
>
> > One more improvement, include also Enum among the derived classes, then
> > you can write
> >
> > months = cycle [Jan .. Dec]
> >
> > Oh, and cycle is also exported from the Prelude, so it's not necessary to
> > import Data.List for that (though you will probably want to imoprt it
> > anyway).
>
> Ohh so many little tasty titbits of Haskell - I was trying for ages to
> get the '..' operator to work. I guess I will start to know where to
> look for these guys as time goes on.

The '..' things are syntactic sugar for enumerations:

[a .. ] === enumFrom a
[a, b .. ] === enumFromThen a b
[a .. b] === enumFromTo a b
[a, b .. c] === enumFromThenTom a b c

they are methods of class Enum.

:i Enum

in ghci or hugs gives the class information (methods and instances currently
in scope).

One place to look for such things is the Haskell report, also many tutorials
and books have a sectioned 'Overview of standard type classes' or some such,
there you should find this and similarly important things.

Another method is to ask ghci or hugs - you have to do it the right way, which
is not always obvious - as in

Prelude> :t \a b -> [a .. b]
\a b -> [a .. b] :: (Enum t) => t -> t -> [t]

so you know you have to look at Enum
Prelude> :i Enum
class Enum a where
  succ :: a -> a
  pred :: a -> a
  toEnum :: Int -> a
  fromEnum :: a -> Int
  enumFrom :: a -> [a]
  enumFromThen :: a -> a -> [a]
  enumFromTo :: a -> a -> [a]
  enumFromThenTo :: a -> a -> a -> [a]
        -- Defined in GHC.Enum
instance Enum Integer -- Defined in GHC.Num
instance Enum Float -- Defined in GHC.Float
instance Enum Double -- Defined in GHC.Float
instance Enum Bool -- Defined in GHC.Enum
instance Enum Ordering -- Defined in GHC.Enum
instance Enum Char -- Defined in GHC.Enum
instance Enum () -- Defined in GHC.Enum
instance Enum Int -- Defined in GHC.Enum

looking at this, you don't see '..', but you see two functions with the
correct type, that it's more likely to be enumFromTo rather than enumFromThen
can easily be inferred from the functions' names.

>
> Cheers,
>
> Philip

Cheers,
Daniel

Reply | Threaded
Open this post in threaded view
|

Re: Defeating type inference

Will Ness-2
In reply to this post by Philip Scott
Philip Scott <pscott <at> foo.me.uk> writes:

>
> Hi Alex,
> > The problem is that when you go fro
> >> months = range (Jan,Dec) : months
> >> realmonths = concat months
> >>    

Another way to go about this is to always look at types. You've correctly
surmised that you have to refer back to the name you're defining, months, in a
recusive definition, so let's write it down as
  months = range (Jan,Dec) `somehowJoinWith` months

What is somehowJoinWith's type? Its first argument is [Month], let's call it
[a]. So
 somehowJoinWith :: [a] -> b -> b

But you want its result to be a list of Month's too. So b = [a] and
 somehowJoinWith :: [a] -> [a] -> [a]

Cons (:) simply won't fit here, as it is :: a -> [a] -> [a].

(++) OTOH does fit, and is exactly what you need.

Thinking with types helps clarify the problem always. It helps us not to
confuse oranges and boxes-of-oranges. :)

Cheers,

Reply | Threaded
Open this post in threaded view
|

Re: Defeating type inference

Will Ness-2
In reply to this post by Philip Scott
Philip Scott <pscott <at> foo.me.uk> writes:

>
> So I puzzled for a little bit about how to do this in the most Haskelly
> way and I thought of this
>
> months = concat (range (Jan, Dec) : months)
>
> Which should work, right**
>
> ** though I am pretty sure this is the Wrong Way to do this. I suspect
> concat takes O(n) time - more elegant approaches would be welcomed!
>


Nobody seem to relate to that point. No, it's not O(n) time. It's O(1) time.
It's just one lazy definition. The _access_ is O(n) and the definition kicks in
at the right time while riding along with the access - take, drop or whatever -
along the list. It is always just taking one head element at a time off the
first list, if not empty, or else switching to the next one - and feeding that
element to list access. If it's not eliminated completely by compilation. :)