Use the loeb function: loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x
To implement a basic spreadsheet processor. The processor should accept input of the form: |##|A |B |C |D |
|01|(* B1 C1)|2 |3 |(* A1 2)|
The output from this example should be: |##|A |B |C |D |
|01|6 |2 |3 |12 |
Cells may contain number literals, references to other cells of the form <letter><number>, or function applications of the form (<function> *<args>).
This is too hard. Can't you do a challenge were you have to calculate the Fibonacci numbers.
Name:
Anonymous2008-05-09 14:11
import qualified Data.Map as M
data Cell a = Num a
| Ref (Char, Int)
| Fun (a -> a -> a) (Cell a) (Cell a)
type Spreadsheet a = M.Map (Char, Int) a
eval :: Cell a -> Spreadsheet a -> a
eval (Num x) s = x
eval (Ref l) s = s M.! l
eval (Fun f x y) s = f (eval x s) (eval y s)
loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x
process :: Spreadsheet (Cell a) -> Spreadsheet a
process = loeb . fmap eval
test = M.fromList [(('A', 1), Fun (*) (Ref ('B', 1)) (Ref ('C', 1))),
(('B', 1), Num 2),
(('C', 1), Num 3),
(('D', 1), Fun (*) (Ref ('A', 1)) (Num 2))]
main = print (process test)
Parsing and printing left as an exercise for the reader.
Name:
Anonymous2008-05-09 16:44
OP here, I've got parsing and evaluation, but no writing yet; I'm about as lazy as my language!
module Main where
import Data.Array
import Control.Monad
import Data.List
import System.IO
import Control.Arrow
import qualified Text.ParserCombinators.Parsec as P
(.:) = (.) . (.)
split :: (Eq a) => a -> [a] -> [[a]]
split _ [] = [[]]
split delim (x:xs) | x == delim = [] : rest
| otherwise = (x : head rest) : tail rest
where rest = split delim xs
remove :: (Eq a) => a -> [a] -> [a]
remove x (y:ys) | x == y = remove x ys
| otherwise = y : remove x ys
remove x [] = []
loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x
type Cell = (Int, Char)
type Symbol = String
type Number = Double
data Expr = LitE Number
| RefE Cell
| AppE Symbol [Expr] deriving (Show)
type Prim = [Number] -> Number
prims :: [(Symbol, Prim)]
prims = map (second binop) $
[("+", (+)), ("-", (-)), ("*", (*)), ("/", (/))]
where binop prim [x, y] = prim x y
parseExpr :: (Monad m) => String -> m Expr
parseExpr x = case P.parse (P.between pad pad expr) [] x of
Left exc -> fail $ show exc
Right x' -> return x'
where expr = P.choice [app, ref, lit]
lit = do first <- (P.try $ sequence [P.char '-', P.digit]) P.<|>
liftM return P.digit
rest <- P.many $ P.digit P.<|> P.char '.'
return $ LitE $ read (first ++ rest)
ref = let column = P.oneOf ['A'..'Z']
row = liftM read $ P.many1 P.digit
in liftM2 (RefE .: flip (,)) column row
app = P.between (P.char '(' >> pad) (pad >> P.char ')') $
liftM2 AppE symbol $ pad >> P.sepBy1 expr pad1
[pad, pad1] = map ($ P.oneOf " \t") [P.many, P.many1]
symbol = let special = P.oneOf "!#$%&|*+-/:<.=>?@^_~"
first = P.letter P.<|> special
rest = P.choice [P.letter, P.digit, special]
in liftM2 (:) first (P.many rest)
type Sheet a = Array Cell a
eval :: Expr -> Sheet Number -> Number
eval (LitE lit) _ = lit
eval (RefE ref) sheet = sheet ! ref
eval (AppE fun args) sheet =
case lookup fun prims of
(Just f) -> f args'
Nothing -> error $ "eval: unknown builtin '" ++ fun ++ "'"
where args' = map (`eval` sheet) args
readSheet :: Handle -> IO (Sheet Expr)
readSheet handle =
do header <- getCells
let columns = map (head . remove ' ') (tail header)
(`unless` fail "readSheet: incorrect header format") $
nub (header !! 0) == "#" && (and $ zipWith (==) ['A'..'Z'] columns)
let loop n rows =
do isEOF <- hIsEOF handle
if isEOF then return $ reverse rows
else do (n':row) <- getCells
when (n /= read n') $
fail "readSheet: row number out of sync"
mapM parseExpr row >>= loop (n + 1) . (:rows)
rows <- loop 1 []
return $ listArray ((1, 'A'), (length rows, last columns)) $ concat rows
where getCells = liftM (remove [] . split '|') $ hGetLine handle
writeSheet :: Handle -> Sheet Number -> IO ()
writeSheet handle sheet = return () -- TODO
process :: Sheet Expr -> Sheet Number
process = loeb . fmap eval
>>5
Jesus shit, this looks like an ass factory exploded. Fucking Haskell mouthbreathers.
Name:
Anonymous2008-05-09 19:47
>>10 ass factory Haskell
You must mean an ass monad. Ass factory explosions are Java code.
Name:
Anonymous2008-05-09 19:59
Monads are a fancy way of composing functions ('binding' them).
A functor is something you can map over, for instance a list.
Loeb takes a functor of functions, applies them to the result of loebing that functor of functions, and returns the functor of results.
>>19
In C you would have to do dependency analysis (a graph problem) to determine the order in which to evaluate cells. In Haskell, you let the compiler do that for you by using loeb. Which is awesome.
Also, I'd like to see a parser/evaluator written in C that is as expressive and concise as the Haskell solution.
SO GO READ K&R, I'LL BE HAVING SEX WITH MY CUTE HASKELL THE DOG.
>>25
In Haskell, the compiler thinks for you. You don't need to think yourself.
Name:
Anonymous2008-05-11 10:06
?
___/|
? \o_O| . o O ( how can you explain loeb in "words" ? )
\ |
f | | ?
|_| |
>Loeb takes a functor of functions, applies them to the result of loebing that functor of functions, and returns the functor of results.
that's basically it, it's a literal translation of the code (heh, i wonder if you could machine-translate haskell :)). but if these words and concepts don't mean anything to you ("functor"?), it won't make things any clearer.
if you want to understand what loeb is all about you'll need more background knowledge (types, you need to know *all* about haskell's type system). here's a thread i started earlier that probably gave rise to this: http://dis.4chan.org/read/prog/1210284504/1- , it contains some more information, but probably not enough so you could get it.
>>29,30
As with any Haskell concept, understanding it is just a matter of getting past all the intellectual masturbation on the part of the tutorial writer.
Loeb permits a set of functions to depend on each other's results in whatever arrangement they need...excluding circular dependencies of course. Each function is given a reference to the whole (unsolved) result set, and when the function tries to read an element of that set, Haskell will recursively solve that function, cache its value, and return it. As a base case, at least one function must ignore its argument.
If you've done any Haskell you've probably exploited this behavior plenty of times. Loeb is just a generalization of it.
(Disclaimer: This is just going by what I've read of it on /prog/.)
>>32
[quote]As with any Haskell concept, understanding it is just a matter of getting past all the intellectual masturbation on the part of the tutorial writer.[/quote]
So true.
>>32
So this magic function that the Haskellites are jizzing everywhere about is just memoization?
Name:
Trollbot90002009-07-01 11:14
sheet processor The processor should accept input of the form f handle param1.
Name:
Anonymous2009-07-01 11:56
>>32
So, loeb gives each function in the functor the entire functor of results of all functions?
Doesn't seem very practical to me.
Name:
Anonymous2009-07-01 12:11
>>57
You just haven't reached our level of Satori yet. You need to lrn2Haskell.
Name:
Anonymous2009-07-01 12:59
>>32 As a base case, at least one function must ignore its argument.
Well, not exactly: loeb [length] = [1]. And then there's loeb [(1:) . head] = [repeat 1], or loeb [(1:) . head . tail, (2:) . head] = [cycle [1,2]].
Name:
hasklol2009-07-01 14:02
>>8
Haskell was made without side-effects (lol pure). Then everyone was like, "Fuck, we need sonuvabitching side-effects to do any goddamn thing!" So they let them back in. But then they were like, "Shit, lazy evaluation means crap is happening in fucked-up ways we can't motherfucking cocksucking asshole dick predict!" Hence, monads.
IOW: Monads are a way of [doing what every other language already does by] separating purity and impurity in a lazy language.
>>60
Nice try, thanks for playing. Monads actually have nothing to do with laziness, and everything to do with passing around arguments you don't care about, especially in recursive code.
Name:
!MILKRIBS4k2009-07-01 16:23
I don't "get" what is up with this HASKELL meme! Why is it so good! Is it better than C! Why is it not on as many platforms as C if it's so good! Is this all just a /prog/ meme!
Name:
Anonymous2009-07-01 16:29
>>63
You have no idea what you're getting into. If you tried to understand Haskell, your head (do anuses have heads?) would explode.
>>66
What I am trying to say now is that you should learn to use the question mark.
And please don't compare Haskell to /b/.
Also, how the hell is /b/ like a secret club?
>>69 JEEPERS CREEPERS! I just read the wiki on FACTORIALS and I did not understand one thing it said!
Name:
Anonymous2009-07-01 17:00
>>69 f@(_:fs) = 0 : 1 : zipWith (+) f fs FACTORIALS!
4/10, I nearly didn't notice.
Name:
Anonymous2009-07-01 18:32
>>62 Nice try
So, 4/10? 5/10? Monads actually have nothing to do with laziness...
Ah, 10/10.
Name:
Anonymous2009-07-01 21:44
>>68 loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x
Name:
Anonymous2009-07-01 21:52
>>72
It's true. Monads are a constuction in category theory.
Name:
Anonymous2009-07-01 22:16
>>72
You have in fact not been trolled. Haskell's monads are completely orthogonal to laziness; in fact, Haskell has some strict monads.
Now if you wanted to implement monads in a language without closures, then you'd be fucked. It would be like trying to compile Ruby.
Name:
Anonymous2009-07-01 22:25
>>75 not been trolled
Lessee: XD
Stupid smiley? Check. Laziness and monads
Tying together completely unrelated things? Check. So then they were like...
Fake history? Check. >>8
Responding to a post from a zillion years ago? Check.
>>82 Could not deduce (Functor m) from the context (Monad m)
arising from a use of `fmap' at <interactive>:1:13-16
Possible fix:
add (Functor m) to the context of an expression type signature
In the first argument of `(.)', namely `fmap'
In the second argument of `(=<<)', namely `fmap . flip id'
In the first argument of `fix', namely `(fmap . flip id =<<)'
Name:
Anonymous2009-07-02 5:05
new challenge: write the loeb function in a language that isn't haskell, and use it to do something useful.
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy