Hello loyal readers: Inside 206-105 has a new theme! I’m retiring Manifest, which was a pretty nice theme but (1) the text size was too small and (2) I decided I didn’t really like the fonts, I’ve reskinned my blog with a theme based on Brent Jackson’s Ashley, but ported to work on WordPress. I hope you like it, and please report any rendering snafus you might notice on older pages. Thanks!
Hi everyone, I'm teaching myself Haskell on the occasional weekend, and recently I decided to implement an interview question. It goes like this:A student in the University Of Ouagadougou has to reach 100 credits or more, in order to get a degree. You're given two dictionaries (hash-maps): 1) A mapping of course-id to course-credits, signifying how many credits each course provides 2) A mapping of course-id to a list of prerequisite course-ids, signifying which other courses must be taken before you could take that course. Write a program that finds the smallest set of courses that will earn you a degree.
I recognized it as a simple search problem. Because I'm a novice in Haskell, I started by writing a solution in Python, so I can wrap my head around it, and then translated it to Haskell. The resulting Haskell implementation works, produces the correct result, and is relatively terse. However, it runs slower than the Python implementation! I must be doing something wrong, but I can't figure out what it is.
Here are the two implementation:
(They include a similar initialization of the hash-maps, just so there's something to run on)
I would really appreciate any help, and also any other comments about my haskell code! Thanks
u/bgamari refactored the code into a much faster version, simply by using IntSet and HashSet. Here's his commentsubmitted by erez27
[link] [43 comments]
At Zalora, we write a lot of web services and web applications in general. We use scotty a lot. And after having written a couple of web-services, despite some small handy abstractions we came up with, it really felt like we could achieve the same thing in a very concise and minimalist manner, by letting the compiler do more work for us so that we would just have to write wrapper for our SQL queries in haskell. All we had to do was to take advantage of a couple of extensions that landed in GHC in the past few years and propagate the right bits of information at the type-level. And this is what we’ve done.
The result is servant (github, hackage), which lets you declare resources, which just represent a bunch of operations (think endpoints) that operate on some type. So you could for example declare a users resource that supports adding, deleting and listing users in the following way:mkResource "users" ctx exceptions & addWith addUser & deleteWith deleteUser & listAllWith listUsers
- ctx is just there to specify how to get our hand on our database connection for example, think of it as a withConnection function
- exceptions is a bunch of functions that catch exceptions of various types and turns them into an error type of yours
- addUser, deleteUser and listUsers are functions that run the corresponding SQL queries using the connection provided by ctx
And now you can turn this into a JSON-based webservice by simply applying Servant.Scotty.runResource to this simple definition. Then, provided you have written a handful of instances as required by each operation, you’ll have a small REST-y webservice with 3 endpoints that do what you expect.
The more interesting aspect of servant however is that the add, delete and listall operations just happen to be some prelude operations provided by the servant packages. You can define your own in just the same way the standard ones are defined. The same applies to the automatic JSON-based request body/response body handling or to the web-framework backend used (we only have a scotty one for now but you could write your own for any other framework by drawing some inspiration from the scotty one). You can extend servant in basically every possible direction.
If you want to learn more about servant, how it can be used and how it works, you may be interested to check out the README from github which contains some documentation links, that I’ll reproduce here:
- Getting started with servant, which guides you through building the simple webservice we’ve seen above. There’s an example in the repository with the code covered in this getting started guide, with a cabal file and everything.
- Tutorial, which dives much more into servant’s packages and modules and its inner workings, with some illustrations of the extensibility of servant.
- Haddocks for all servant packages
We would of course be glad to hear any kind of feedback, so please do not hesitate to shoot us an email with comments, and report any issue you may encounter on our github.Posted on July 26, 2014
I'm looking for an API for lazy streaming of monadic data structures. I.e., I need to convert a datastructure into something that can traverse it partially and accumulate transformations instead of applying them. To be more specific I want to extend the API of the "stm-containers" library, with a function which will stream the elements of a container in such a way.
Now, of course, it could be implemented using a library like "pipes", e.g. with a function having a signature like the following:producer :: Map k v -> Producer (k, v) STM ()
But it obviously would be an overkill, which would bind the library to a specific IO streaming ecosystem.
What I'm looking for is a simpler streaming API, using which I could implement a function like the following:stream :: Map k v -> Stream STM (k, v)
And then to be able to lazily manipulate streams (filter, map, join - what not). I guess, this is what the ListT monad transformer is supposed to do, but I never dived into it and I know that it's notorious for being broken. The "pipes" library claims to provide a proper version of this transformer, but then again it binds the user to the "pipes" ecosystem.
So my question is: is there a library that solves this problem or am I missing something evident in the approach to my problem?submitted by nikita-volkov
[link] [30 comments]
Lets say you have the type class:class Foo a where f :: a -> String g :: a -> Int k :: a -> Bool
So none of the functions are defined by default. Yet I can do the following:module MyMod (Foo(f)) where ...
And it compiles! Not even a warning? People can import this module, make an instance for their types yet only be able to define f. Then when they compile their code, they'll get the warning that k and g are not defined. Yet they can't possibly define k or g!
How come ghc/haskell allows this? Is there any instance where this would be desirable? I would think that it shouldn't allow you to partially export functions in a typeclass if those functions don't have a default implementation.submitted by Die-Nacht
[link] [10 comments]
I've been trying to push management in the Haskell direction for development and while I could address most concerns there were a few that seem like deal breakers (here are the two main ones):
Memory allocation - real time safety critical code usually has significant hardware limitations and it is not an option to allow for the possibility of memory errors: heap, stack
Compiler certification - while verifying the correctness of the application code is one thing, the method of proving the object code generated by the compiler is a whole new bag of worms.
Can anyone help me address these concerns?
Edit: Thanks for the feedback everyone! I have a lot of resources to research, so far:
I've looked at everything at a high level and the resources: COMPCERT and Atom address the issues above and Copilot seems to add nice functionality on top of Atom. I still have to figure out if/what can work together and what projects such as SMACCM add to the above technologies.submitted by Azsu
[link] [21 comments]
Hey guys, I'm a 21 year old that has been programming in one way or the other since I was 11 and about 6 months ago I found Haskell and fell absolutely in love. I've read 3 books so far, countless academic papers and blog posts and I've been using Project Euler and random 'itches' I find in day to day work to learn the language, and I'm still insatiable for more! I've always liked to program, but Haskell helped me realize that it is my passion, and I would love for this to become more than a hobby.
Here's the problem though: I have no idea where to start. I have little founding in academia or industry as I'm almost entirely self taught. How do I get my name out there, and prove that I'm a viable candidate? I have my High School diploma and no work experience related to programming, but I know that if I get an interview I can prove that I'm worth my salt. I've contributed to many public projects over the years and I have a personal project or two under my belt, but I am in want of experience working in a group setting.
I know Haskell, C, C++, ARM assembly(albeit an older dialect, ARMv4), Bash, Emacs Lisp, GML, bits of Java, Python, LaTeX, and probably more that I'm forgetting. I'm also familiar with Windows, Linux, and Mac OS X development and I am capable of maintaining a cross-platform code base.
I am particularly interested in the realm of gaming and compilers, particularly GHC. I'm learning more about the architecture of GHC currently so as to help port it to Android. I have a working draft, thanks to Neurocyte, but it isn't without its problems yet :)
You can view my Github here: https://github.com/MP2E/
I welcome any criticisms, advise, or even stories of how you got into the industry. At this point, I'm willing to look outside the box and work outside of Functional Programming as well, if need be :P
EDIT: Probably should have mentioned, I live in Las Vegas, NV. I'd prefer to either work locally or remotely, rather than relocate.. Relocation might be an option though :Vsubmitted by rezb1t
[link] [2 comments]
Hi, I am a newbie to Haskell and do sincerely need help with the following: I want to write a function isPal :: String -> Bool that determines if the argument string is a palindrome.
Eg. "Able was I ere I saw Elba" "A man, a plan, a canal, Panama!"
Where the first argument string is a "pure palindrome", if we ignore case differences, and could be tested with a simple function like:
isPurePal xs = xs == reverse xs
The second argument string will fail the simple test because it has extra punctuation and the spaces fall in different positions when read in different directions.
I need help to write a function that will work for both the above cases, and other cases that involve the inclusion of spaces, punctuation, and case differences.
Note: I am thinking of using the class predicates in the Char library, but this is my first haskell program and am not too sure how to format my arguments.
Please any help would be sincerely appreciated.
Cheers.submitted by yamis144100
[link] [14 comments]