More than one way to skin a cat question - repeat

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

More than one way to skin a cat question - repeat

acomber
LYAH beginner on page 55.

What I try to do is see the heading of a section, eg repeat function and
then try to come up with my own version before looking at books
implementation.

Here is my implementation:

repeat' :: a -> [a]
repeat' x = [x] ++ repeat' x

Here is books:

repeat' :: a -> [a]
repeat' x = x:repeat' x

Mine appears to work.  Is mine just as good?  Are there problems with my
way?  Is books way more idiomatic Haskell?

I want to learn the best approaches hence my question.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130411/63ad7d49/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

More than one way to skin a cat question - repeat

Benjamin Edwards
(:) is O(1), (++) is O(n). Try and implement (++) and it should be easy to
see why.
On 11 Apr 2013 10:44, "Angus Comber" <anguscomber at gmail.com> wrote:

> LYAH beginner on page 55.
>
> What I try to do is see the heading of a section, eg repeat function and
> then try to come up with my own version before looking at books
> implementation.
>
> Here is my implementation:
>
> repeat' :: a -> [a]
> repeat' x = [x] ++ repeat' x
>
> Here is books:
>
> repeat' :: a -> [a]
> repeat' x = x:repeat' x
>
> Mine appears to work.  Is mine just as good?  Are there problems with my
> way?  Is books way more idiomatic Haskell?
>
> I want to learn the best approaches hence my question.
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130411/d74bbf38/attachment-0001.htm>

Reply | Threaded
Open this post in threaded view
|

More than one way to skin a cat question - repeat

Thomas Davie

On 11 Apr 2013, at 10:47, Benjamin Edwards <edwards.benj at gmail.com> wrote:

> (:) is O(1), (++) is O(n). Try and implement (++) and it should be easy to see why.
>
(++) is O(n) in the length of it's first argument, which here is a constant 1, so it's O(1).

That said, the book's implementation is *margionally* better.  The implementation using (++) creates the list [x], and then destroys it again, and creates another one when it does the append.  The version using (:) does not do this.

Thanks

Tom Davie


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130411/de6048d1/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

More than one way to skin a cat question - repeat

Brent Yorgey-2
On Thu, Apr 11, 2013 at 10:53:03AM +0100, Tom Davie wrote:

>
> On 11 Apr 2013, at 10:47, Benjamin Edwards <edwards.benj at gmail.com> wrote:
>
> > (:) is O(1), (++) is O(n). Try and implement (++) and it should be easy to see why.
> >
> (++) is O(n) in the length of it's first argument, which here is a constant 1, so it's O(1).
>
> That said, the book's implementation is *margionally* better.  The
> implementation using (++) creates the list [x], and then destroys it
> again, and creates another one when it does the append.  The version
> using (:) does not do this.

Note, however, that it's quite likely the compiler will optimize this
away and they will generate identical code.  (Even if it doesn't, this
is hardly worth worrying about.)  That said, the version with (:) is
indeed more idiomatic.

-Brent