A common use case for Apache + PHP is for simple static sites where you just need to do simple sharing of html fragments (like the header and footer). Is there an example anywhere of using snap and heist to do this? In fact, it could just be wai instead of snap (but I believe that it's more likely that someone has done this with snap). Specifically, what I am looking for is a way to set things up such that I have a directory with heist templates, and routing just takes the path from the URL, and uses it for a template lookup. That's it. No database, no persistence, no auth. I thought that snap init might give me enough to figure this out, but it didn't. I would appreciate any help. Thanks.submitted by andrewthad
[link] [11 comments]
MonadFix is an odd beast; many Haskell programmers will never use it in their careers. It is indeed very rarely that one needs MonadFix; and for that reason, non-contrived cases where MonadFix is needed are quite interesting to consider.
In this article, I’ll introduce MonadFix and show how it can be handy for compiling the Kleene closure (also known as star or repetition) of regular expressions.What is MonadFix?
If you hear about MonadFix for the first time, you might think that it is needed to define recursive monadic actions, just like ordinary fix is used to define recursive functions. That would be a mistake. In fact, fix is just as applicable to monadic actions as it is to functions:guessNumber m = fix $ \repeat -> do putStrLn "Enter a guess" n <- readMaybe <$> getLine if n == Just m then putStrLn "You guessed it!" else do putStrLn "You guessed wrong; try again" repeat
So, what is mfix for? First, recall that in Haskell, one can create recursive definitions not just for functions (which makes sense in other, non-lazy languages) or monadic actions, but for ordinary data structures as well. This is known as cyclic (or circular, or corecursive) definitions; and the technique itself is sometimes referred to as tying the knot.
The classic example of a cyclic definition is the (lazy, infinite) list of Fibonacci numbers:fib = 0 : 1 : zipWith (+) fib (tail fib)
Cyclic definitions are themselves rare in day-to-day Haskell programming; but occasionally, the right hand side will be not a pure value, but a monadic computation that needs to be run in order to obtain the value.
Consider this (contrived) example, where we start the sequence with an arbitrary number entered by the user:fibIO1 = do putStrLn "Enter the start number" start <- read <$> getLine return $ start : 1 : zipWith (+) fibIO1 (tail fibIO1)
This doesn’t typecheck because fibIO is not a list; it’s an IO action that produces a list.
But if we try to run the computation, it doesn’t make much sense either:fibIO2 = do putStrLn "Enter the start number" start <- read <$> getLine fib <- fibIO2 return $ start : 1 : zipWith (+) fib (tail fib)
This version of fibIO will ask you to enter the start number ad infinitum and never get to evaluating anything.
Of course, the simplest thing to do would be to move IO out of the recursive equation; that’s why I said the example was contrived. But MonadFix gives another solution:fibIO3 = mfix $ \fib -> do putStrLn "Enter the start number" start <- read <$> getLine return $ start : 1 : zipWith (+) fib (tail fib)
Or, using the do-rec syntax:fibIO4 = do rec fib <- do putStrLn "Enter the start number" start <- read <$> getLine return $ start : 1 : zipWith (+) fib (tail fib) return fib Compiling regular expressions
As promised, I am going to show you an example usage of MonadFix that solved a problem other than “how could I use MonadFix?”. This came up in my work on regex-applicative.
For a simplified presentation, let’s consider this type of regular expressions:data RE = Sym Char -- symbol | Seq RE RE -- sequence | Alt RE RE -- alternative | Rep RE -- repetition
Our goal is to compile a regular expression into a corresponding NFA. The states will be represented by integer numbers. State 0 corresponds to successful completion; and each Sym inside a regex will have a unique positive state in which we are expecting the corresponding character.type NFAState = Int
The NFA will be represented by a maptype NFA = IntMap (Char, [NFAState])
where each state is mapped to the characters expected at that state and the list of states where we go in case we get the expected character.
To compile a regular expression, we’ll take as an argument the list of states to proceed to when the regular expression as a whole succeeds (otherwise we’d have to compile each subexpression separately and then glue NFAs together). This is essentially the continuation-passing style; only instead of functions, our continuations are NFA states.
During the compilation, we’ll use a stack of two State monads: one to assign sequential state numbers to Syms; the other to keep track of the currently constructred NFA.-- Returns the list of start states and the transition table compile :: RE -> ([NFAState], NFA) compile re = runState (evalStateT (go re ) 0) IntMap.empty -- go accepts exit states, returns entry states go :: RE -> [NFAState] -> StateT NFAState (State NFA) [NFAState] go re exitStates = case re of Sym c -> do !freshState <- gets (+1); put freshState lift $ modify' (IntMap.insert freshState (c, exitStates)) return [freshState] Alt r1 r2 -> (++) <$> go r1 exitStates <*> go r2 exitStates Seq r1 r2 -> go r1 =<< go r2 exitStates
This was easy so far: alternatives share their exit states and their entry states are combined; and consequtive subexpressions are chained. But how do we compile Rep? The exit states of the repeated subexpression should become its own entry states; but we don’t know the entry states until we compile it!
And this is precisely where MonadFix (or recursive do) comes in:Rep r -> do rec let allEntryStates = ownEntryStates ++ exitStates ownEntryStates <- go r allEntryStates return allEntryStates
Why does this circular definition work? If we unwrap the State types, we’ll see that the go function actually computes a triple of three non-strict fields:
- The last used state number
- The list of entry states
- The NFA map
The elements of the triple may depend on each other as long as there are no actual loops during evaluation. One can check that the fields can be indeed evaluated linearly in the order in which they are listed above:
- The used state numbers at each step depend only on the regular expression itself, so it can be computed wihtout knowing the other two fields.
- The list of entry states relies only on the state number information; it doesn’t need to know anything about the NFA transitions.
- The NFA table needs to know the entry and exit states; but that is fine, we can go ahead and compute that information without creating any reverse data dependencies.
An ASM Monad – a similar example from a different domain.
Oliver Charles’s 24 Days of GHC Extensions: Recursive Do.
Levent Erkok’s thesis which contains all you need to know about MonadFix, including several other examples.
Todd Wilson points out that Douglas McIlroy describes a similar regular expression compilation technique in his 2004 JFP Functional Pearl Enumerating the strings of regular languages. Like this article, Douglas’s paper uses a circular definition when compiling the Kleene closure. But the circular definition is not monadic there: instead of using the State monad, Douglas passes the state around by hand.
Speaker list available for Haskell eXchange conference, also announcing 2-day Hackathon (and promo code inside!)
The programme for Haskell eXchange in London Oct 8th-9th, is finally getting settled, we'll have 4 keynotes over the two days from Simon Peyton Jones, Lennart Augustsson, Simon Marlow and Luite Stegeman!
To check out the full list of speakers and their topics, go here:
Descriptions for some of the keynotes are still missing, hopefully it will be updated soon.
We're also announcing that there's going to be a 2-day Hackathon over the following weekend where the focus will be on improving the Haskell infrastructure, anyone should feel free to come and if you're a beginner that wants to start contributing to the Haskell infrastructure, you'll be able to get help from experienced contributors.
Read the full description and register here (it's free):
Finally, if you want to get 25% off on the conference ticket, you can use the promo code HASKELL-EXCHANGE-25, it should be valid until September 12th!
Hope to see you all there! :)submitted by frolsen
[link] [7 comments]
In the Theory Lunch of the last week, James Chapman talked about the MU puzzle from Douglas Hofstadter’s book Gödel, Escher, Bach. This puzzle is about a string rewriting system. James presented a Haskell program that computes derivations of strings. Inspired by this, I wrote my own implementation, with the goal of improving efficiency. This blog post presents this implementation. As usual, it is available as a literate Haskell file, which you can load into GHCi.The puzzle
Let me first describe the MU puzzle shortly. The puzzle deals with strings that may contain the characters , , and . We can derive new strings from old ones using the following rewriting system:
The question is whether it is possible to turn the string into the string using these rules.
You may want to try to solve this puzzle yourself, or you may want to look up the solution on the Wikipedia page.The code
The code is not only concerned with deriving from , but with derivations as such.Preliminaries
We import Data.List:import Data.List Basic things
We define the type Sym of symbols and the type Str of symbol strings:data Sym = M | I | U deriving Eq type Str = [Sym] instance Show Sym where show M = "M" show I = "I" show U = "U" showList str = (concatMap show str ++)
Next, we define the type Rule of rules as well as the list rules that contains all rules:data Rule = R1 | R2 | R3 | R4 deriving Show rules :: [Rule] rules = [R1,R2,R3,R4] Rule application
We first introduce a helper function that takes a string and returns the list of all splits of this string. Thereby, a split of a string str is a pair of strings str1 and str2 such that str1 ++ str2 == str. A straightforward implementation of splitting is as follows:splits' :: Str -> [(Str,Str)] splits' str = zip (inits str) (tails str)
The problem with this implementation is that walking through the result list takes quadratic time, even if the elements of the list are left unevaluated. The following implementation solves this problem:splits :: Str -> [(Str,Str)] splits str = zip (map (flip take str) [0 ..]) (tails str)
Next, we define a helper function replace. An expression replace old new str yields the list of all strings that can be constructed by replacing the string old inside str by new.replace :: Str -> Str -> Str -> [Str] replace old new str = [front ++ new ++ rear | (front,rest) <- splits str, old `isPrefixOf` rest, let rear = drop (length old) rest]
We are now ready to implement the function apply, which performs rule application. This function takes a rule and a string and produces all strings that can be derived from the given string using the given rule exactly once.apply :: Rule -> Str -> [Str] apply R1 str | last str == I = [str ++ [U]] apply R2 (M : tail) = [M : tail ++ tail] apply R3 str = replace [I,I,I] [U] str apply R4 str = replace [U,U]  str apply _ _ =  Derivation trees
Now we want to build derivation trees. A derivation tree for a string str has the following properties:
- The root is labeled with str.
- The subtrees of the root are the derivation trees for the strings that can be generated from str by a single rule application.
- The edges from the root to its subtrees are marked with the respective rules that are applied.
We first define types for representing derivation trees:data DTree = DTree Str [DSub] data DSub = DSub Rule DTree
Now we define the function dTree that turns a string into its derivation tree:dTree :: Str -> DTree dTree str = DTree str [DSub rule subtree | rule <- rules, subStr <- apply rule str, let subtree = dTree subStr] Derivations
A derivation is a sequence of strings with rules between them such that each rule takes the string before it to the string after it. We define types for representing derivations:data Deriv = Deriv [DStep] Str data DStep = DStep Str Rule instance Show Deriv where show (Deriv steps goal) = " " ++ concatMap show steps ++ show goal ++ "\n" showList derivs = (concatMap ((++ "\n") . show) derivs ++) instance Show DStep where show (DStep origin rule) = show origin ++ "\n-> (" ++ show rule ++ ") "
Now we implement a function derivs that converts a derivation tree into the list of all derivations that start with the tree’s root label. The function derivs traverses the tree in breadth-first order.derivs :: DTree -> [Deriv] derivs tree = worker [(,tree)] where worker :: [([DStep],DTree)] -> [Deriv] worker tasks = rootDerivs tasks ++ worker (subtasks tasks) rootDerivs :: [([DStep],DTree)] -> [Deriv] rootDerivs tasks = [Deriv (reverse revSteps) root | (revSteps,DTree root _) <- tasks] subtasks :: [([DStep],DTree)] -> [([DStep],DTree)] subtasks tasks = [(DStep root rule : revSteps,subtree) | (revSteps,DTree root subs) <- tasks, DSub rule subtree <- subs]
Finally, we implement the function derivations which takes two strings and returns the list of those derivations that turn the first string into the second:derivations :: Str -> Str -> [Deriv] derivations start end = [deriv | deriv@(Deriv _ goal) <- derivs (dTree start), goal == end]
You may want to enter
derivations [M,I] [M,U,I]
at the GHCi prompt to see the derivations function in action. You can also enter
derivations [M,I] [M,U]
to get an idea about the solution to the MU puzzle.
Tagged: Douglas Hofstadter, functional programming, Gödel, Escher, Bach (book), Haskell, Institute of Cybernetics, James Chapman, literate programming, MU puzzle, string rewriting, talk, Theory Lunch
More than two years ago, my colleague Denis Firsov and I gave a series of three Theory Lunch talks about the MIU string rewriting system from Douglas Hofstadter’s MU puzzle. The first talk was about a Haskell implementation of MIU, the second talk was an introduction to the functional logic programming language Curry, and the third talk was about a Curry implementation of MIU. The blog articles MIU in Haskell and A taste of Curry are write-ups of the first two talks. However, a write-up of the third talk has never seen the light of day so far. This is changed with this article.
I want to thank all the people from the Curry mailing list who have helped me improving the code in this article.Preliminaries
We import the module SearchTree:import SearchTree Basic things
We define the type Sym of symbols and the type Str of symbol strings:data Sym = M | I | U showSym :: Sym -> String showSym M = "M" showSym I = "I" showSym U = "U" type Str = [Sym] showStr :: Str -> String showStr str = concatMap showSym str
Next, we define the type Rule of rules:data Rule = R1 | R2 | R3 | R4 showRule :: Rule -> String showRule R1 = "R1" showRule R2 = "R2" showRule R3 = "R3" showRule R4 = "R4"
So far, the Curry code is basically the same as the Haskell code. However, this is going to change below.Rule application
Rule application becomes a lot simpler in Curry. In fact, we can code the rewriting rules almost directly to get a rule application function:applyRule :: Rule -> Str -> Str applyRule R1 (init ++ [I]) = init ++ [I, U] applyRule R2 ([M] ++ tail) = [M] ++ tail ++ tail applyRule R3 (pre ++ [I, I, I] ++ post) = pre ++ [U] ++ post applyRule R4 (pre ++ [U, U] ++ post) = pre ++ post
Note that we do not return a list of derivable strings, as we did in the Haskell solution. Instead, we use the fact that functions in Curry are nondeterministic.
Furthermore, we do not need the helper functions splits and replace that we used in the Haskell implementation. Instead, we use the ++-operator in conjunction with functional patterns to achieve the same functionality.
Now we implement a utility function applyRules for repeated rule application. Our implementation uses a similar trick as the famous Haskell implementation of the Fibonacci sequence:applyRules :: [Rule] -> Str -> [Str] applyRules rules str = tail strs where strs = str : zipWith applyRule rules strs
The Haskell implementation does not need the applyRules function, but it needs a lot of code about derivation trees instead. In the Curry solution, derivation trees are implicit, thanks to nondeterminism.Derivations
A derivation is a sequence of strings with rules between them such that each rule takes the string before it to the string after it. We define types for representing derivations:data Deriv = Deriv [DStep] Str data DStep = DStep Str Rule showDeriv :: Deriv -> String showDeriv (Deriv steps goal) = " " ++ concatMap showDStep steps ++ showStr goal ++ "\n" showDerivs :: [Deriv] -> String showDerivs derivs = concatMap ((++ "\n") . showDeriv) derivs showDStep :: DStep -> String showDStep (DStep origin rule) = showStr origin ++ "\n-> (" ++ showRule rule ++ ") "
Now we implement a function derivation that takes two strings and returns the derivations that turn the first string into the second:derivation :: Str -> Str -> Deriv derivation start end | start : applyRules rules start =:= init ++ [end] = Deriv (zipWith DStep init rules) end where rules :: [Rule] rules free init :: [Str] init free
Finally, we define a function printDerivations that explicitly invokes a breadth-first search to compute and ultimately print derivations:printDerivations :: Str -> Str -> IO () printDerivations start end = do searchTree <- getSearchTree (derivation start end) putStr $ showDerivs (allValuesBFS searchTree)
You may want to enter
printDerivations [M, I] [M, I, U]
at the KiCS2 prompt to see the derivations function in action.
Tagged: breadth-first search, Curry, Denis Firsov, Douglas Hofstadter, functional logic programming, functional pattern, functional programming, Haskell, Institute of Cybernetics, KiCS2, literate programming, logic programming, MU puzzle, string rewriting, talk, Theory Lunch
hi, i am really interested in learning Haskell. can you recommend something good video tutorials/screencasts where there is a project/product not only basic syntax.submitted by Cosaquee
[link] [3 comments]
I have some CLI tools developped in Haskell, that I need some of my college at work to use. He doesn't know anything about programming and even command line, but the only things he will need to do , is build the tool (I can help him), modifies some configuration file , launch the tool and open the result in Excel.
I was thinking first of using Docker, but he need to open the file on Excel. My experience with Docker on Mac is that it's a bit of pain to share files between a container and the Mac. Is it the same on windows ?
Otherwise I was thinking stack would be a good solution (as it seems to also install ghc). However, AFAIR using the command line on Windows is not great. Could I use cygwin and stack on windows ?
What would you recommend ?submitted by maxigit
[link] [24 comments]
For example OverloadedStrings, BangPattern, MultiWayIf, LambdaCase, etc. I think that there are extensions that will not hurt much old software and they could be disabled for old compilations. But this could improve new versions of GHC and give some direction.submitted by varosi
[link] [17 comments]