Categories
Tutorial

A Spreadsheet in Reflex

I recently came across a list of challenging projects. Most seemed like something I had already done; but the spreadsheet caught my eye. Since I wanted to learn more about Reflex anyway, why not do it in Reflex?

First: the model as a DAG

If you don’t care about the model you can jump right to the next section. Here’s an overview over the API we will build in this section:

data Coord -- the coordinates of a cell
data Expr -- an expression in a cell
parseExpr :: String -> Maybe Expr
data Sheet -- a spreadsheet as a directed acyclic graph
data EvalError = CyclicDependencies [Coord]
emptySheet :: Sheet
update :: Coord -> Expr -> Sheet -> Either EvalError Sheet
lookupCoord :: Coord -> Sheet -> Maybe Int

Lets start by building a language for expressions:

data Coord = Coord String Int
  deriving (Eq, Ord)

instance Show Coord where
  show (Coord s i) = map toUpper s ++ show i

instance Read Coord where
  readPrec = parens $ prec 10 $ do
    s <- lift $ munch1 isUpper
    n <- lift $ readDecP
    pure $ Coord s n

data Expr
  = IntVal Int
  | Add Expr Expr
  | Times Expr Expr
  | Dependency Coord
  deriving (Eq, Ord)

instance Show Expr where
  show (IntVal i) = show i
  show (Add e1 e2) = show e1 ++ "+" ++ show e2
  show (Times e1 e2) = show e1 ++ "*" ++ show e2
  show (Dependency d) = show d

instance Read Expr where
  readPrec = parens $
    (prec 10 $ IntVal <$> lift readDecP)
    +++ (prec 10 $ Dependency <$> readPrec)
    +++ (prec 5 $ do
      e1 <- step readPrec
      Symbol "+" <- lexP
      e2 <- readPrec
      pure $ Add e1 e2)
    +++ (prec 6 $ do
      e1 <- step readPrec
      Symbol "*" <- lexP
      e2 <- readPrec
      pure $ Times e1 e2)

parseExpr :: String -> Maybe Expr
parseExpr = go . filter (/=' ')
  where
    go "" = Just $ IntVal 0
    go s  = readMaybe s

The Read and Show instances allow us to parse and display expressions. We also accept the empty string, since Nothing stands for a parse failure here and an empty cell should have value 0.

Lets build a model for our spreadsheet next! Since cells may depend on each other we need to build a directed acyclic graph of dependencies.

newtype Sheet = Sheet { unSheet :: Map Coord Cell }
  deriving (Eq, Ord, Show)

data Cell = Cell
  { cellDeps :: Set Coord -- ^ cells that this depends on
  , cellFounds :: Set Coord -- ^ cells that depend on this
  , cellExpr :: Expr
  , cellValue :: Int
  }  deriving (Eq, Ord, Show)

data EvalError 
  = CyclicDependencies [Coord]
  deriving (Eq, Ord, Show)

We can connect this to our expressions:

evaluate :: Expr -> Sheet -> Int
evaluate e (Sheet m) = go e
  where
    go (IntVal i) = i
    go (Dependency d) = case Map.lookup d m of
      Nothing -> 0
      Just c -> cellValue c
    go (Add e1 e2) = go e1 + go e2
    go (Times e1 e2) = go e1 * go e2

dependencies :: Expr -> Set Coord
dependencies = go mempty
  where
    go acc (IntVal _) = acc
    go acc (Add e1 e2) = go (go acc e1) e2
    go acc (Times e1 e2) = go (go acc e1) e2
    go acc (Dependency d) = Set.insert d acc

We will start with an empty map as our sheet and add new cells as they are being written or referenced. We can handle input by calling the update function:

nullCell :: Cell
nullCell = Cell mempty mempty (IntVal 0) 0

addDependency :: Coord -> Coord -> Sheet -> Sheet
addDependency parent child (Sheet m) =
  let c = Map.findWithDefault nullCell child m 
  in Sheet $ Map.insert child 
       (c { cellFounds = Set.insert parent $ cellFounds c }) m

update :: Coord -> Expr -> Sheet -> Either EvalError Sheet
update p e (Sheet m) = case Map.lookup p m of
  Just c -> recompute p $ go (cellFounds c) -- see below for recompute
  Nothing -> Right (go mempty)
  where
    value = evaluate e (Sheet m)
    newDeps = dependencies e
    newCell founds = Cell newDeps founds e value
    go founds = Sheet $ Map.insert p (newCell founds) $ unSheet $
      foldl' (\m d -> addDependency p d m) (Sheet m) newDeps

When a cell changed we need to recompute all cells that depend on this cell recursively. If we encounter our original cell in the process we have a cycle and report it. We will assume though that every cycle in our graph must involve p, e.g. that the graph was acyclic before we updated p.

data RecomputeState = RecomputeState
  { currentPath :: [Coord]
  , uptodate :: Set Coord
  , todos :: Set Coord
  , currentSheet :: Sheet
  } deriving (Eq, Ord, Show)

-- | Compute all cells that depend on p.
recompute :: Coord -> Sheet -> Either EvalError Sheet
recompute p sheet = fmap (currentSheet . snd) $ runExcept
  $ runStateT (mapM_ go (cellFounds pCell)) 
              (RecomputeState [] mempty (cellFounds pCell) sheet)
  where
    pCell = fromMaybe nullCell $ Map.lookup p $ unSheet sheet
    go q = do
      s <- get
      when (q == p) $ 
        throwError $ CyclicDependencies $ (q:) $ currentPath s
      when (q `Set.member` uptodate s) $ pure ()
      let nCell = fromMaybe nullCell $ Map.lookup q 
                $ unSheet $ currentSheet s
      mapM_ go $ Set.toList $ Set.intersection (cellDeps nCell) (todos s)
      s <- get
      let v = evaluate (cellExpr nCell) (currentSheet s)
      put $ s
        { todos = (cellFounds nCell) <> Set.delete q (todos s)
        , currentPath = q : currentPath s
        , currentSheet = Sheet $ Map.insert q (nCell {cellValue = v}) 
                       $ unSheet $ currentSheet s
        , uptodate = Set.insert q (uptodate s)
        }
      mapM_ go (cellFounds nCell)
      s <- get
      put $ s { currentPath = tail $ currentPath s }

Adding a Reflex UI

The most basic component in our spreadsheet is going to be a single cell. It shows the value of the corresponding cell in the spreadsheet when not focused and the corresponding expression when focused. Furthermore we want the cell to have an hasError attribute when an error occurred.

cell :: (DomBuilder t m, MonadFix m, MonadHold t m)
     => Coord -> Dynamic t Bool -> Dynamic t Sheet -> m (Event t Expr)
cell coord errored sheet = mdo
  expr <- holdDyn "" $ gate (current $ _inputElement_hasFocus input)
    $ _inputElement_input input
  let value = (maybe "" (T.pack . show) . lookupCoord coord) <$> sheet
  let view = _inputElement_hasFocus input >>= \b ->
        if b then expr else value
  let cur = (parseExpr . T.unpack) <$> expr
  let err = (&&) <$> (not <$> _inputElement_hasFocus input) 
                 <*> ((||) <$> errored <*> (isNothing <$> cur))
  input <- inputElement
    $ modifyAttributes .~
      ((\b -> "hasError" =: if b then Just "" else Nothing) <$> updated err)
    $ def & inputElementConfig_setValue .~ updated view
  pure $ fmapMaybe id $ updated cur

It is remarkable how readable the code is once you get used to it. value is always the value of the cell in the sheet, expr is the content of the input field when it has focus. We set the value of the input field to view. If the field doesn’t have focus and we either couldn’t parse the expression or get an error signal from outside, the field gets the attribute hasError.

A grid is just a collection of cells plus some extra state:

grid :: (DomBuilder t m, MonadFix m, MonadHold t m) 
     => m (Dynamic t Sheet)
grid = mdo
  sheet <- holdDyn emptySheet (fmapMaybe (either (const Nothing) Just) 
    $ attachWith (flip ($)) (current sheet) changes)
  cycle <- holdDyn [] -- a possible cycle in the definitions
    $ fmapMaybe (either (\(CyclicDependencies d) -> Just d) (\_ -> Just []))
    $ attachWith (flip ($)) (current sheet) changes
  el "tr" $ sequence_ $ (el "th" (text "")) :
    [ el "th" (text (T.pack (a:[]))) | a <- ['A'..'B']]
  cs <- concat <$> sequenceA
    [ el "tr" $ sequenceA $ (el "td" (text (T.pack (show n)) >> pure never))
    : [ el "td" $ fmap (c, ) <$> cell c ((c `elem`) <$> cycle) sheet
      | a <- ['A'..'B'], let c = read (a:(show n))]
    | n <- [1..4]]
  let changes = mergeWith (\f g s -> f s >>= g)
        $ map (fmap (\(p,e) -> update p e)) cs
  pure sheet

We pass an error code to the cell if it is part of a cycle. We make sure to arrange the cells in a table with headers.

Finally, we just plug the grid into our site and we are done!

frontend :: Frontend (R FrontendRoute)
frontend = Frontend
  { _frontend_head = do 
      el "title" $ text "Literally Excel!"
      el "style" $ text "input[hasError] { border: 3px solid red; } "
  , _frontend_body = do
      _ <- grid
      return ()
  }

Conclusion

I am still unsure, whether I would build a bigger project with Reflex. On the one hand, the cell widget above would have been a lot harder to build in any other language and I am impressed by the ease with which it is possible to pass state around. But there are some pain-points:

  • The documentation isn’t that good. When I first looked at InputElement I thought that _inputElement_input referred to the input as typed by the user with one event for every character. Then I thought that _inputElement_input == updated _inputElement_value. Both are wrong and I am still not sure what _inputElement_value does.
  • My current solution is unbearably slow on normal-sized spreadsheets (26*100 cells). It seems like reflex is adding all the input elements to the dom and then needs a few seconds to place them at the right location and add the event handlers.

Still, it feels like reflex is getting more usable: Thanks to Obelisk installing it is now a breeze and there are enough tutorials to get started. If you are interested in FRP you should give Reflex a try!

Leave a Reply

Your email address will not be published. Required fields are marked *