[Haskell-cafe] Ultra-newbie Question
Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Thanks in advance. ctauss ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On 18 September 2010 17:51, Christopher Tauss ctau...@gmail.com wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Easiest way I can think of: n_lastn n = reverse . take n . reverse Alternatively: n_lastn n xs = drop (len - n) xs where len = length xs -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Unified Haskell login
On Fri, 2010-09-17 at 08:47 +0200, Michael Snoyman wrote: Hi cafe, Let me preface this by stating that this is purposely a half-baked idea, a straw man if you will. I'd like to hear what the community thinks about this. I mentioned yesterday that I was planning on building haskellers.com. The first technicality I considered was how login should work. There are a few basic ideas: * Username/password on the site. But who wants to deal with *another* password? * OpenID. Fixes the extra password problem, but doesn't give us any extra information about the user (email address, etc). Actually most OpenID providers uses OpenID extension which allows to query (with user permission) about data such as e-mail address, real name etc. * Facebook/Twitter/Google: We get the users email address, but do we *really* want to force users to have one of those accounts? Possibly also: * FOAF/SSL: Practically not used in wild I'd give +1 for either common username/password or OpenID. Regards signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] haltavista - look for functions by example
Hello, I just hacked together something I've been talking about a while ago on that mailing list. It's a program that looks for functions given a set of input/outputs. Example session 1: brau...@worf:~$ haltavista 2 2 4 EOF Prelude (*) Prelude (+) Prelude (^) Example session 2 (refining previous search): brau...@worf:~$ haltavista 2 2 4 1 2 3 EOF Prelude (+) Example session 3 (higher-order functions): brau...@worf:~$ haltavista (+1) (+2) (1,1) (2,3) EOF Data.Graph.Inductive.Query.Monad () Under the hood, uses: - hint for type inference; - hoogle to get a list of candidate functions; - hint for testing. Hoogle calling facility has been copy-pasted (and later modified) from the Yi project. It's availaible on github (http://github.com/polux/haltavista) and I plan to release it on hackage as soon as I catch stack overflows that occur during testing using hint. So far I didn't manage to do it, even by catching asynchronous exceptions. Every suggestion/help is welcome. Also, if I got something wrong with the licences (Yi uses GPL-2 and code is copy-pasted, Hint BSD3 and is linked, Hoogle is called as an external process, haltavista is GPL-3 for now) please tell me. Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Here is a more manual way to do it, hopefully this shows the approach required. You don't need to store anything, just keep removing the head of the list until its of the size you want. n_lastn :: Int - [a] - [a] n_lastn n xs = let len = length xs - n drp = if len 0 then 0 else len rmv 0ys = ys rmv m (y:ys) = rmv (m - 1) ys in rmv drp xs Cheers, David On 18 September 2010 17:51, Christopher Tauss ctau...@gmail.com wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Thanks in advance. ctauss ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: Re: Full strict functor by abusing Haskell exceptions
On Sep 17, 2010, at 10:39 PM, Ben Franksen wrote: What I actually wanted was a mathematical definition, though. Here's a definition of pointed objects: http://ncatlab.org/nlab/show/pointed+object -- Sjoerd Visscher sjo...@w3future.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] translating bidirectional fundeps to TFs
On Fri, Sep 17, 2010 at 10:19 PM, Dan Doel dan.d...@gmail.com wrote:
On Friday 17 September 2010 4:04:26 pm Gábor Lehel wrote:
What I would *want* to write is this:
class (Mutable (Thawed a), Frozen (Thawed a) ~ a) = Immutable a where
type Thawed a :: *
thaw :: a - Thawed a
class (Immutable (Frozen a), Thawed (Frozen a) ~ a) = Mutable a where
type Frozen a :: *
freeze :: a - Frozen a
This looks considerably nicer, but it's not valid -- I get a cycle in
class declarations via superclasses error, on the one hand, and (if I
remove that) an infinite loop in the typechecker (context reduction
stack overflow) on the other (FlexibleContexts being a prerequisite
for most of the interesting things you can do with TypeFamilies).
So what should one, theoretically, do here? Is there a way to express
this using TypeFamilies which preserves both the semantics and the
symmetry of the FDs version, and is also valid? Or should one just go
ahead and use the FDs because, in this case, they're simply better
suited? *Or* should one just suck it up and go with the ugly
TypeFamilies version because TypeFamilies are The Future*?
What about:
class (Thawed frozen ~ thawed, Frozen thawed ~ frozen)
= TwoPhase thawed frozen where
type Thawed frozen :: *
type Frozen thawed :: *
thaw :: frozen - thawed
freeze :: thawed - frozen
This is the translation I'd expect for the fundep. And ideally, in the future,
you could use the original class with fundeps as sugar for the above, because
fundeps are a nice way of expressing mutual dependency like this (just as
associated types are nicer than making the associated type a class parameter
as is required by fundeps).
Hmm. I had a similar thought, but dismissed it because I was under the
impression that you needed to use all the parameters of the class as
parameters of its associated types. But apparently that was mistaken
-- or, at least, your example compiles. :)
The redundancy is sort of annoying ('thawed' and 'Thawed frozen' both
being necessary and necessarily equivalent). This is a case where
associated type defaults would be helpful, to eliminate at least some
of it (namely, having to define Thawed and Frozen in every instance,
even though only one definition is possible). Anyway, it's a shame you
can't really decouple the two halves as in my nonworking example, but
this is nicer than the other alternative I had. Thanks!
-- Dan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Work is punishment for failing to procrastinate effectively.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Am 18.09.2010 09:51, schrieb Christopher Tauss: I am trying to write a function that takes a list and returns the last n elements. last_n n = fst . foldr step ([], n) where step _ (xs, 0) = (xs, 0) step x (xs, n) = (x:xs, n-1) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Uniting graphics libraries
Hi, I have nearly finished writing a Collada-output library to make 3d animation files. Before doing this I have looked at two libraries on hackage that parse Collada to display it. For my library I have copied the types from gpipe-collada and extended them. Now I am thinking that it would be nice if all 3d libraries would use the same data type. Currently gpipe-collada, graphics-formats-collada, obj, ... parse 3d-formats. FieldTrip, lambdacube-engine, ... (to mention examples) can generate and/or display 3d-objects. But they all cannot be combined without tedious type conversions. The obvious argument is that every application has its own needs. This is of course true but I think that the Collada format shows how to deal with this (you can do quite a lot with profile_common). I would be willing to write patches for some libraries and make a discussable 3d-types library based on Collada. Hope you agree, Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Uniting graphics libraries
2010/9/18 Tillmann Vogt tillmann.v...@rwth-aachen.de: Hi, I have nearly finished writing a Collada-output library to make 3d animation files. Before doing this I have looked at two libraries on hackage that parse Collada to display it. For my library I have copied the types from gpipe-collada and extended them. Now I am thinking that it would be nice if all 3d libraries would use the same data type. Currently gpipe-collada, graphics-formats-collada, obj, ... parse 3d-formats. FieldTrip, lambdacube-engine, ... (to mention examples) can generate and/or display 3d-objects. But they all cannot be combined without tedious type conversions. The obvious argument is that every application has its own needs. This is of course true but I think that the Collada format shows how to deal with this (you can do quite a lot with profile_common). I would be willing to write patches for some libraries and make a discussable 3d-types library based on Collada. Hi, This is a great goal! I've also been thinking in solidifying all things 3D on hackage lately and forming a game and graphics strike team. (The idea is that even if you're not interested in games, there are still a lot of common things.) Now it seems you see Collada as a good common starting point. I don't know much about Collada and I can't really say if it is a good idea or not. But by following the blender development mailing list, it seems people don't really 'trust' it, in the sense that in practice, it is still difficult to move things around between different programs through Collada... Also Collada is (I am not sure) just an interchange format and you talk about data types. Can you be a bit more specific about what you envision? Are they a direct representation of Collada? You talk about combining the different libraries on Hackage, would you like to do it through Collada? When I said I thought about solidifying things lately, I was thinking to the problem you describe but at a lower level: for instance there are many different representations for 3D vectors and transforms. Is it also a concern for you? Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Uniting graphics libraries
Am 18.09.2010 15:14, schrieb Vo Minh Thu: Hi, This is a great goal! I've also been thinking in solidifying all things 3D on hackage lately and forming a game and graphics strike team. (The idea is that even if you're not interested in games, there are still a lot of common things.) Now it seems you see Collada as a good common starting point. I don't know much about Collada and I can't really say if it is a good idea or not. But by following the blender development mailing list, it seems people don't really 'trust' it, in the sense that in practice, it is still difficult to move things around between different programs through Collada... Maybe the format isn't properly implemented in some programs. I have also experienced examples-files that didn't load. But it think that collada is currently the best format and it's quite powerful (shaders, physics, ...). Also Collada is (I am not sure) just an interchange format and you talk about data types. Can you be a bit more specific about what you envision? Are they a direct representation of Collada? Yes, pretty much a direct representation. But some things can be made simpler. I.e. I replace the instance_ tags with their value and have a type garantee instead of trusting that a url referenced object exists. The Collada people stress the point that its only an interchange format. But Google is using it also for delivery (Google Earth). If one can live with some seconds longer loading it is no problem. By the way wonder why Collada isn't advocating binary XML? That would make things faster. You talk about combining the different libraries on Hackage, would you like to do it through Collada? Yes, the types . I currently don't see a better way. When I said I thought about solidifying things lately, I was thinking to the problem you describe but at a lower level: for instance there are many different representations for 3D vectors and transforms. Is it also a concern for you? This is a problem. But I would accept a majority vote. At the moment I would use the same vector library as gpipe. Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Uniting graphics libraries
2010/9/18 Tillmann Vogt tillmann.v...@rwth-aachen.de: Am 18.09.2010 15:14, schrieb Vo Minh Thu: Hi, This is a great goal! I've also been thinking in solidifying all things 3D on hackage lately and forming a game and graphics strike team. (The idea is that even if you're not interested in games, there are still a lot of common things.) Now it seems you see Collada as a good common starting point. I don't know much about Collada and I can't really say if it is a good idea or not. But by following the blender development mailing list, it seems people don't really 'trust' it, in the sense that in practice, it is still difficult to move things around between different programs through Collada... Maybe the format isn't properly implemented in some programs. I have also experienced examples-files that didn't load. But it think that collada is currently the best format and it's quite powerful (shaders, physics, ...). Also Collada is (I am not sure) just an interchange format and you talk about data types. Can you be a bit more specific about what you envision? Are they a direct representation of Collada? Yes, pretty much a direct representation. But some things can be made simpler. I.e. I replace the instance_ tags with their value and have a type garantee instead of trusting that a url referenced object exists. The Collada people stress the point that its only an interchange format. But Google is using it also for delivery (Google Earth). If one can live with some seconds longer loading it is no problem. By the way wonder why Collada isn't advocating binary XML? That would make things faster. You talk about combining the different libraries on Hackage, would you like to do it through Collada? Yes, the types . I currently don't see a better way. Ok. I'll learn more about Collada then. Is your code already available somewhere? Still, Collada seems to be on a far end of the spectrum of what could be unified. I mean, say your animation has to be rendered by some Haskell code, do you wish to go through Collada or that your animation code and the rendering code share some other data structures than Collada (Or maybe Collada is just a first step?) ? If the later, it would be useful to share what those other data structures should be. When I said I thought about solidifying things lately, I was thinking to the problem you describe but at a lower level: for instance there are many different representations for 3D vectors and transforms. Is it also a concern for you? This is a problem. But I would accept a majority vote. At the moment I would use the same vector library as gpipe. Why a majority vote? Maybe we can do better: state some desired properties, benchmark the existing libraries and see if something fits? Are there other people interested in unifying the efforts here? Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Uniting graphics libraries
Am 18.09.2010 16:16, schrieb Vo Minh Thu: Ok. I'll learn more about Collada then. Is your code already available somewhere? I will upload it in a few days on hackage. It is not finished yet. Still, Collada seems to be on a far end of the spectrum of what could be unified. I mean, say your animation has to be rendered by some Haskell code, do you wish to go through Collada or that your animation code and the rendering code share some other data structures than Collada (Or maybe Collada is just a first step?) ? If the later, it would be useful to share what those other data structures should be. Animations in Collada are streams of interpolated floats that are interpreted as time or output (i.e. angle of a rotation). The output is then channeled to the tags of the nodes. One can do quite a lot with this. At the moment I can't image what else one could do. When I said I thought about solidifying things lately, I was thinking to the problem you describe but at a lower level: for instance there are many different representations for 3D vectors and transforms. Is it also a concern for you? This is a problem. But I would accept a majority vote. At the moment I would use the same vector library as gpipe. Why a majority vote? Maybe we can do better: state some desired properties, benchmark the existing libraries and see if something fits? Are there other people interested in unifying the efforts here? Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Web development work
Cool, an API sounds great. I favor a RESTful API, so most likely it would simply be JSON served via the same URL as the main page; jus set the Accept header appropriately. Does that sound good enough? Michael On Fri, Sep 17, 2010 at 5:21 PM, Jeremy Shaw jer...@n-heptane.com wrote: I have been meaning to add a jobs section to the happstack.com website. It would be nice if haskellers.com had an API so I could syndicate just the happstack related jobs/contractors/etc on happstack.com. That would help bring more exposure to haskellers.com, and would be beneficial for visitors to happstack.com who do not know about haskellers.com and are concerned that it would be hard to find developers. Obviously, I can just provide a link -- but an API would be nice. - jeremy On Sep 16, 2010, at 7:35 AM, Michael Snoyman wrote: On Thu, Sep 16, 2010 at 10:26 AM, Andrew Coppin andrewcop...@btinternet.com wrote: On 16/09/2010 08:52 AM, Michael Snoyman wrote: future it would be beneficial to the community to have this information centralized on a website. I think it would be useful to have some basic skills and experience information, including system administration abilities. [..] (And yes, given the frequency with which this gets asked, we should probably write this info down somewhere!) OK, I'll bite on this one. I just registered the domain name haskellers.com (I was surprised it was available). So let me ask the community what information they would want out there. Here's the ideas I had: * Users can create their own profiles. Profiles have the following information: * Basic name, contact, website, photo, etc. * Brief bio * Skills. We'll probably have a list of skills to choose from. * Notable projects worked on, with strong focus on Hackage packages. * Some kind of web of trust feature, where users can confirm that someone else's profile is accurate. Open to suggestions on this. * A public message board for posting job information. I think this would not require login to post, but we would have spam protection (recaptcha). And then of course the basic what is Haskell, links to haskell.org, etc. I'll probably be able to get started on this early next week. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On 09/18/2010 02:51 AM, Christopher Tauss wrote: I am trying to write a function that takes a list and returns the last n elements. This may just be for the sake of learning, in which case this is fine, but usually, needing to do this would be a sign that you are using lists improperly (since this is a O(n) time operation). Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] n_lastn n = reverse . take n . reverse - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Thanks you Ivan and David for clarifying this. Best Regards, Chris On Sat, Sep 18, 2010 at 3:55 AM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 18 September 2010 17:51, Christopher Tauss ctau...@gmail.com wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Easiest way I can think of: n_lastn n = reverse . take n . reverse Alternatively: n_lastn n xs = drop (len - n) xs where len = length xs -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com http://ivanmiljenovic.wordpress.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Ultra-newbie Question
On Sat, 2010-09-18 at 03:51 -0400, Christopher Tauss wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Thanks in advance. ctauss I'll add my $0.03 - unless you are doing it to learn about lists rethink your approach. Taking k elements from end of n-element list will be O(n) operation. For example with appropriate structures (like finger trees) it would look like O(k) operation. Regards signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: happstack-auth-0.2
Am 17.09.2010 22:06, schrieb Nils Schweinsberg: [1] http://hackage.haskell.org/package/happstack-auth Hackage fails to build this package: http://hackage.haskell.org/packages/archive/happstack-auth/0.2/logs/failure/ghc-6.12 However, Crypto == 4.* should be on hackage: http://hackage.haskell.org/package/Crypto-4.2.1 Is there anything I can do with my package to get this to build? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: happstack-auth-0.2
On Sat, Sep 18, 2010 at 08:19:33PM +0200, Nils Schweinsberg wrote: Am 17.09.2010 22:06, schrieb Nils Schweinsberg: [1] http://hackage.haskell.org/package/happstack-auth Hackage fails to build this package: http://hackage.haskell.org/packages/archive/happstack-auth/0.2/logs/failure/ghc-6.12 However, Crypto == 4.* should be on hackage: http://hackage.haskell.org/package/Crypto-4.2.1 Is there anything I can do with my package to get this to build? Unfortunately Crypto-4.2.1 was broken by the latest version of QuickCheck (2.3), which introduced Arbitrary instances for the Word types: http://hackage.haskell.org/packages/archive/Crypto/4.2.1/logs/failure/ghc-6.12 A new release of Crypto, without those instances, is needed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: happstack-auth-0.2
Why are you using Crypto? I'm hoping to make Crypto as we know it obsolete. To that end, I've been working on a unified interface (crypto-api) and after the algorithms packages catch up I planned to make a meta package crypto-algs. Cheers, Thomas On Sat, Sep 18, 2010 at 11:19 AM, Nils Schweinsberg m...@n-sch.de wrote: Am 17.09.2010 22:06, schrieb Nils Schweinsberg: [1] http://hackage.haskell.org/package/happstack-auth Hackage fails to build this package: http://hackage.haskell.org/packages/archive/happstack-auth/0.2/logs/failure/ghc-6.12 However, Crypto == 4.* should be on hackage: http://hackage.haskell.org/package/Crypto-4.2.1 Is there anything I can do with my package to get this to build? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On Saturday 18 September 2010 19:44:38, Jake McArthur wrote: On 09/18/2010 02:51 AM, Christopher Tauss wrote: I am trying to write a function that takes a list and returns the last n elements. This may just be for the sake of learning, in which case this is fine, but usually, needing to do this would be a sign that you are using lists improperly (since this is a O(n) time operation). By which he meant O(length list), not the number of elements you're asking for. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). That will be a problem for long lists (consider n_lastn 10 [1 .. 10^8]). You can implement it as an O(n) [the number of elements you want] *space* operation, provided that the list is generated lazily and not referred to by anything else, but the code is decidedly less nice: The first idea would be to keep a window of n elements and move it to the end of the list: n_lastn n xs = case splitAt n xs of (ys,[]) - ys -- the list contains at most n elements, yay (ys,zs) - loop ys zs where loop window [] = window loop window (v:vs) = loop (tail window ++ [v]) vs The space behaviour is now fine (if compiled with optimisations), but unfortunately, the time complexity has become O(n*length list) because the (++)-calls are left-nested: Suppose n = 4, loop (1:2:3:4:[]) [5 .. end] ~ loop ((2:3:4:[]) ++ [5]) [6 .. end] ~ loop (2:((3:4:[]) ++ [5])) [6 .. end] ~ loop (((3:4:[]) ++ [5]) ++ [6]) [7 .. end] The strictness analyser has been smart enough to transform the call to tail into a strict pattern match on window, as if we'd written loop (_:twindow) (v:vs) = loop (twindow ++ [v]) vs so the first few tails go fast, but later, we have to go through more layers to get at the head of the window to discard it ~ loop ((3:((4:[]) ++ [5])) ++ [6]) [7 .. end] ~ loop (3:(((4:[]) ++ [5]) ++ [6])) [7 .. end] -- finally! ~ loop 4:[]) ++ [5]) ++ [6]) ++ [7]) [8 .. end] -- bubble the 4 through four layers of parentheses: ~ loop(((4:([] ++ [5])) ++ [6]) ++ [7]) [8 .. end] ~ loop ((4:(([] ++ [5]) ++ [6])) ++ [7]) [8 .. end] ~ loop (4:((([] ++ [5]) ++ [6]) ++ [7])) [8 .. end] ~ loop [] ++ [5]) ++ [6]) ++ [7]) ++ [8]) [9 .. end] -- phew -- form now on, it's uniform, on each step we have to match an expression [] ++ [a]) ++ [b]) ++ [c]) ++ [d]) against (_:rest) 1. check whether ((([] ++ [a]) ++ [b]) ++ [c]) is empty, for that, 2. check whether (([] ++ [a]) ++ [b]) is empty, for that, 3. check whether ([] ++ [a]) is empty, for that, 4. check whether [] is empty, it is, hence [] ++ [a] = [a], 5. check whether [a] is empty, it's not, it's (a:[]), hence 6. (...) ++ [b] = a:([] ++ [b]), so 2's not empty, and 7. (...) ++ [c] = a:(([] ++ [b]) ++ [c]), so 1's not empty and 8. (...) ++ [d] = a:((([] ++ [b]) ++ [c]) ++ [d]) 9. at last, a can be dropped and we get to loop [] ++ [b]) ++ [c]) ++ [d]) ++ [e]) remainingList Blech! Appending to the end of a list is bad if it leads to left-nested parentheses (it's okay if the parentheses are right-nested). So we might be tempted to keep the window reversed and cons each element to the front, dropping the last. No good, removing an element from the end is O(length window) too. One possibility to fix it is to use a 'list-like' type with O(1) appending at the end and dropping from the front. Data.Sequence is such a type, import qualified Data.Sequence as Seq import Data.Foldable (toList) import Data.Sequence (ViewL(..), (|)) n_lastn' :: Int - [a] - [a] n_lastn' k _ | k = 0= [] n_lastn' k xs = case splitAt k xs of (ys,[]) - ys (ys,zs) - go (Seq.fromList ys) zs where go acc [] = toList acc go acc (v:vs) = case Seq.viewl acc of _ : keep - go (keep | v) vs _ - error teh impossible jus hapnd fixes space and time behaviour. But the constant factors for Sequence are larger than those for lists, so we can beat it with lists: n_lastn :: Int - [a] - [a] n_lastn k _ | k = 0 = [] n_lastn k xs = case splitAt k xs of (ys,[]) - ys (ys,zs) - go k (reverse ys) zs where m = k-1 go _ acc [] = reverse $ take k acc go 0 acc (v:vs) = case splitAt m acc of (keep,release) - release `seq` go k (v:keep) vs go h acc (v:vs) = go (h-1) (v:acc) vs Every k steps, we perform the O(k) operation of removing the last (k+1) elements from a (2k)-element list, making the removal from the end an amortized O(1) operation. You can trade some space for speed and clip the window in larger intervals, say every (3*k) or every (10*k) steps. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org
Re: [Haskell-cafe] translating bidirectional fundeps to TFs
On Saturday 18 September 2010 8:27:45 am Gábor Lehel wrote: Hmm. I had a similar thought, but dismissed it because I was under the impression that you needed to use all the parameters of the class as parameters of its associated types. But apparently that was mistaken -- or, at least, your example compiles. :) Classes of the form I sent: class (T1 b ~ a, T2 a ~ b) = C a b where type T1 b :: * type T2 a :: * ... actually desugar into the following: type family T1 b :: * type family T2 a :: * class (T1 b ~ a, T2 a ~ b) = C a b where ... So the parameters of the families needn't match the parameters of the class. It does impose some additional constraint on your making instances of the families whenever you make an instance of the class, which wouldn't be there if you wrote them separately, but I think that's it. This is also important when translating classes like the following: class Closed a | - a where ... You can only write a single instance of that class (although, I'd guess that GHC currently accepts 'instance Closed a where ...', which should be illegal). To translate it to type families, you write: class Closed a where type T :: * ... a family with no parameters. The compiler will only allow you to write one instance for that family, but you must provide an instance for each instance of the Closed class. Hence, you can only write a single instance of the Closed class. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
I think this is O(n) time, O(1) space (!). lastk :: Int - [a] - [a] lastk k xs = last $ zipWith const (properTails xs) (drop k xs) where properTails = tail . tails Luke On Sat, Sep 18, 2010 at 1:51 PM, Daniel Fischer daniel.is.fisc...@web.de wrote: On Saturday 18 September 2010 19:44:38, Jake McArthur wrote: On 09/18/2010 02:51 AM, Christopher Tauss wrote: I am trying to write a function that takes a list and returns the last n elements. This may just be for the sake of learning, in which case this is fine, but usually, needing to do this would be a sign that you are using lists improperly (since this is a O(n) time operation). By which he meant O(length list), not the number of elements you're asking for. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). That will be a problem for long lists (consider n_lastn 10 [1 .. 10^8]). You can implement it as an O(n) [the number of elements you want] *space* operation, provided that the list is generated lazily and not referred to by anything else, but the code is decidedly less nice: The first idea would be to keep a window of n elements and move it to the end of the list: n_lastn n xs = case splitAt n xs of (ys,[]) - ys -- the list contains at most n elements, yay (ys,zs) - loop ys zs where loop window [] = window loop window (v:vs) = loop (tail window ++ [v]) vs The space behaviour is now fine (if compiled with optimisations), but unfortunately, the time complexity has become O(n*length list) because the (++)-calls are left-nested: Suppose n = 4, loop (1:2:3:4:[]) [5 .. end] ~ loop ((2:3:4:[]) ++ [5]) [6 .. end] ~ loop (2:((3:4:[]) ++ [5])) [6 .. end] ~ loop (((3:4:[]) ++ [5]) ++ [6]) [7 .. end] The strictness analyser has been smart enough to transform the call to tail into a strict pattern match on window, as if we'd written loop (_:twindow) (v:vs) = loop (twindow ++ [v]) vs so the first few tails go fast, but later, we have to go through more layers to get at the head of the window to discard it ~ loop ((3:((4:[]) ++ [5])) ++ [6]) [7 .. end] ~ loop (3:(((4:[]) ++ [5]) ++ [6])) [7 .. end] -- finally! ~ loop 4:[]) ++ [5]) ++ [6]) ++ [7]) [8 .. end] -- bubble the 4 through four layers of parentheses: ~ loop(((4:([] ++ [5])) ++ [6]) ++ [7]) [8 .. end] ~ loop ((4:(([] ++ [5]) ++ [6])) ++ [7]) [8 .. end] ~ loop (4:((([] ++ [5]) ++ [6]) ++ [7])) [8 .. end] ~ loop [] ++ [5]) ++ [6]) ++ [7]) ++ [8]) [9 .. end] -- phew -- form now on, it's uniform, on each step we have to match an expression [] ++ [a]) ++ [b]) ++ [c]) ++ [d]) against (_:rest) 1. check whether ((([] ++ [a]) ++ [b]) ++ [c]) is empty, for that, 2. check whether (([] ++ [a]) ++ [b]) is empty, for that, 3. check whether ([] ++ [a]) is empty, for that, 4. check whether [] is empty, it is, hence [] ++ [a] = [a], 5. check whether [a] is empty, it's not, it's (a:[]), hence 6. (...) ++ [b] = a:([] ++ [b]), so 2's not empty, and 7. (...) ++ [c] = a:(([] ++ [b]) ++ [c]), so 1's not empty and 8. (...) ++ [d] = a:((([] ++ [b]) ++ [c]) ++ [d]) 9. at last, a can be dropped and we get to loop [] ++ [b]) ++ [c]) ++ [d]) ++ [e]) remainingList Blech! Appending to the end of a list is bad if it leads to left-nested parentheses (it's okay if the parentheses are right-nested). So we might be tempted to keep the window reversed and cons each element to the front, dropping the last. No good, removing an element from the end is O(length window) too. One possibility to fix it is to use a 'list-like' type with O(1) appending at the end and dropping from the front. Data.Sequence is such a type, import qualified Data.Sequence as Seq import Data.Foldable (toList) import Data.Sequence (ViewL(..), (|)) n_lastn' :: Int - [a] - [a] n_lastn' k _ | k = 0 = [] n_lastn' k xs = case splitAt k xs of (ys,[]) - ys (ys,zs) - go (Seq.fromList ys) zs where go acc [] = toList acc go acc (v:vs) = case Seq.viewl acc of _ : keep - go (keep | v) vs _ - error teh impossible jus hapnd fixes space and time behaviour. But the constant factors for Sequence are larger than those for lists, so we can beat it with lists: n_lastn :: Int - [a] - [a] n_lastn k _ | k = 0 = [] n_lastn k xs = case splitAt k xs of (ys,[]) - ys (ys,zs) - go k (reverse ys) zs where m = k-1 go _ acc [] = reverse $ take k acc go 0 acc (v:vs) = case splitAt m acc of (keep,release) - release `seq` go k (v:keep) vs go h acc (v:vs) = go (h-1) (v:acc) vs Every k steps, we perform the O(k) operation of removing the last (k+1) elements from a (2k)-element list,
Re: [Haskell-cafe] Ultra-newbie Question
On Saturday 18 September 2010 22:42:57, Luke Palmer wrote:
I think this is O(n) time, O(1) space (!).
lastk :: Int - [a] - [a]
lastk k xs = last $ zipWith const (properTails xs) (drop k xs)
where properTails = tail . tails
Luke
No, it's O(k) too. You zip [[x_n, x_{n+1}, ... ], ... ] with
[x_{n+k}, ... ], so all of [x_n, ..., x_{n+k}] stays in memory.
It's *very* nice though, and scales better than my stuff (but my stuff is
faster for small k [ 1000, here, YMMV]).
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On Sep 18, 2010, at 12:51 AM, Christopher Tauss wrote: I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. Note that keeping just the suffix is the same as dropping the prefix. Consider your data: A finite list. The length of the suffix to keep. An algebraic relationship between lengths of lists, suffixes, and their prefixes: length(prefix) + length(suffix) = legnth(list) Putting all of this together: n_tail n list = drop (prefix_length) list where prefix_length = length list - n You may be interested in how drop is carrying around some state: drop n xs | n = 0 = xs drop _ [] = [] drop n (_:xs) = drop (n-1) xs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Web development work
A RESTful API with JSON results sounds perfect. I will be surprised if the API useful for 3rd party sites happens to map on to the URL structure used by the main site. But if that works, all the better :) Of course, if your site which is creating the JSON is written in Haskell, and my site which is using it is written in Haskell, then it would be nice if I could somehow benefit from the haskell type checker telling me that you have changed your JSON a bit. In some small experimental RESTful-ish sites a I have made I tend to make the return values of the API be an algrebraic data type that all the API functions return. Then I have functions like SiteRetVal - JSON, SiteRetVal - XML, etc, which makes it easy to convert the output to whatever format the client wants. With a system like that, it is possible to have the SiteRetVal be in it's own hackage library. Your site and my site would both depend on that package. Then when you change the API return values, I get a new version of that library to type-check against... Not sure how valuable/feasible it is in practice though. I have only developed a prototype far enough to determine that it *can* be done. Whether it *should* be done remains to be seen. Also, there maybe be some issues with using the accept header. In theory, you may someday provide XML (in addition to JSON). But I think that some browsers list xml has a higher preference than html. So then normal browser users will start getting xml instead of html? Anyway, the basic idea of a simple RESTful API with JSON is exactly what I was hoping for. The rest is implementation details, which I don't care much about as long as it works. I definitely do not want to turn this into a design by committee project. Also, once the site is 'done', it would be nice to hirer a graphic designer to give it a nice, clean, professional look. - jeremy On Sep 18, 2010, at 12:28 PM, Michael Snoyman wrote: Cool, an API sounds great. I favor a RESTful API, so most likely it would simply be JSON served via the same URL as the main page; jus set the Accept header appropriately. Does that sound good enough? Michael On Fri, Sep 17, 2010 at 5:21 PM, Jeremy Shaw jer...@n-heptane.com wrote: I have been meaning to add a jobs section to the happstack.com website. It would be nice if haskellers.com had an API so I could syndicate just the happstack related jobs/contractors/etc on happstack.com. That would help bring more exposure to haskellers.com, and would be beneficial for visitors to happstack.com who do not know about haskellers.com and are concerned that it would be hard to find developers. Obviously, I can just provide a link -- but an API would be nice. - jeremy On Sep 16, 2010, at 7:35 AM, Michael Snoyman wrote: On Thu, Sep 16, 2010 at 10:26 AM, Andrew Coppin andrewcop...@btinternet.com wrote: On 16/09/2010 08:52 AM, Michael Snoyman wrote: future it would be beneficial to the community to have this information centralized on a website. I think it would be useful to have some basic skills and experience information, including system administration abilities. [..] (And yes, given the frequency with which this gets asked, we should probably write this info down somewhere!) OK, I'll bite on this one. I just registered the domain name haskellers.com (I was surprised it was available). So let me ask the community what information they would want out there. Here's the ideas I had: * Users can create their own profiles. Profiles have the following information: * Basic name, contact, website, photo, etc. * Brief bio * Skills. We'll probably have a list of skills to choose from. * Notable projects worked on, with strong focus on Hackage packages. * Some kind of web of trust feature, where users can confirm that someone else's profile is accurate. Open to suggestions on this. * A public message board for posting job information. I think this would not require login to post, but we would have spam protection (recaptcha). And then of course the basic what is Haskell, links to haskell.org, etc. I'll probably be able to get started on this early next week. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: Re: Full strict functor by abusing Haskell exceptions
On 9/18/10 8:00 AM, Sjoerd Visscher wrote: On Sep 17, 2010, at 10:39 PM, Ben Franksen wrote: What I actually wanted was a mathematical definition, though. Here's a definition of pointed objects: http://ncatlab.org/nlab/show/pointed+object pointed objects, pointed sets/groups/topospaces, pointed categories, pointed functors, etc aren't all the same though. The Joy of Cats[1] has info on all of them except pointed functors. [1] http://katmat.math.uni-bremen.de/acc/acc.pdf -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: malicious JS on haskell site
Popup advertising is still being hosted on haskell.org. What is the right way to deal with this? Is there a person or process to fix this? Deleting some nedstatbasic javascript at the bottom should fix the problem. I'm sorry for sending this to such a large list but I don't know who the is the right contact and it seems like a pretty bad way to start off with people who are trying to figure out what haskell offers. Thanks, Keith On Thu, Sep 9, 2010 at 5:30 PM, Keith Sheppard keiths...@gmail.com wrote: Hello cafe, Maybe malicious isn't the right word but there is a JS based web counter on http://www.haskell.org/complex/why_does_haskell_matter.html which likes to show pop up adverts. They must have switched over from counting visitors to showing adverts at some point since the web page was created. I'm sure this is something we want removed... It would probably be good to grep the whole server to make sure that this counter doesn't show up on some other page too. Sorry if this is a simple oversight on my part but I don't know who I should be contacting about this kind of thing. It would be great if there was some kind of webmas...@haskell.org address that was advertised or some form that we could submit for issues like this. -keith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: Re: Full strict functor by abusing Haskell exceptions
On Saturday 18 September 2010 6:03:39 pm wren ng thornton wrote: pointed objects, pointed sets/groups/topospaces, pointed categories, pointed functors, etc aren't all the same though. The definition of pointed objects could be massaged to yield pointed functors, though. Instead of a category with a terminal object, we could relax the definition to include categories with a distinguished object I. Then, a pointed object in such a category is an object X together with x : I - X. This isn't always very interesting. For any category with an initial object 0, the category of objects pointed over 0 is isomorphic to the original category, for instance. However, categories with arbitrary distinguished objects could be viewed as a precursor to monoidal categories, and pointed objects are then precursors to monoid objects. And then when you instantiate all that to the category of endofunctors over some category, you get pointed functors being precursors to monads. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Web development work
On Sat, Sep 18, 2010 at 11:47 PM, Jeremy Shaw jer...@n-heptane.com wrote: A RESTful API with JSON results sounds perfect. I will be surprised if the API useful for 3rd party sites happens to map on to the URL structure used by the main site. But if that works, all the better :) Of course, if your site which is creating the JSON is written in Haskell, and my site which is using it is written in Haskell, then it would be nice if I could somehow benefit from the haskell type checker telling me that you have changed your JSON a bit. In some small experimental RESTful-ish sites a I have made I tend to make the return values of the API be an algrebraic data type that all the API functions return. Then I have functions like SiteRetVal - JSON, SiteRetVal - XML, etc, which makes it easy to convert the output to whatever format the client wants. With a system like that, it is possible to have the SiteRetVal be in it's own hackage library. Your site and my site would both depend on that package. Then when you change the API return values, I get a new version of that library to type-check against... Not sure how valuable/feasible it is in practice though. I have only developed a prototype far enough to determine that it *can* be done. Whether it *should* be done remains to be seen. There's one better: in addition to providing JSON output, I could provide the output of the default Show typeclass (call the mimetype x-text/haskell-show?), and then you can just use a readMay on your end. Still using the intermediate package idea. Also, there maybe be some issues with using the accept header. In theory, you may someday provide XML (in addition to JSON). But I think that some browsers list xml has a higher preference than html. So then normal browser users will start getting xml instead of html? I don't think any browsers list text/xml by default, rather application/xhtml+xml, though I could be wrong. Anyway, the basic idea of a simple RESTful API with JSON is exactly what I was hoping for. The rest is implementation details, which I don't care much about as long as it works. I definitely do not want to turn this into a design by committee project. Also, once the site is 'done', it would be nice to hirer a graphic designer to give it a nice, clean, professional look. Of course, if we want to make this an enterprise project, we would do the graphic design by committee. I think blue is a nice color Yes, but isn't that excluding the 50.23% of our target audience that's female? Do women not like blue? Let's take a vote, all in favor of women not liking blue? ... OK, so as not be gender specific, we'll use a black background with mauve text. Sounds like a good idea to me. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Ultra-newbie Question
Translation: Look at Data.Sequence sometime. On 9/18/10 11:15 AM, Maciej Piechotka wrote: On Sat, 2010-09-18 at 03:51 -0400, Christopher Tauss wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Thanks in advance. ctauss I'll add my $0.03 - unless you are doing it to learn about lists rethink your approach. Taking k elements from end of n-element list will be O(n) operation. For example with appropriate structures (like finger trees) it would look like O(k) operation. Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Ultra-newbie Question
Translation: Look at Data.Sequence sometime. On 9/18/10 11:15 AM, Maciej Piechotka wrote: On Sat, 2010-09-18 at 03:51 -0400, Christopher Tauss wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Thanks in advance. ctauss I'll add my $0.03 - unless you are doing it to learn about lists rethink your approach. Taking k elements from end of n-element list will be O(n) operation. For example with appropriate structures (like finger trees) it would look like O(k) operation. Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
