CODEWITHSUNDEEP
haskell
Carcigenicate
Carcigenicate

Reputation: 45726

How can I write this as implicit recursion?

I'm trying to write a module that can take a string representation of a simple equation, and evaluate it. As a first step, I need to cut the equation into individual tokens; based on the "rules" of takePiece. I tried writing cutEqu as a fold, but ran into the problem that I'm not really folding over the string; I'm taking different sized pieces until it's exhausted. I could cheat and make it fold over a list of numbers equal to the length of the string, but that seems clumsy.

In most of the guides I've read, they note that explicit recursion is a rare occurrence once you understand implicit recursive patterns (like folds and maps), and this seems like a potentially common scenario, but can't find an appropriate standard function to handle it. How would someone go about writing something simple like cutEqu using implicit recursion? I'm sure I could figure out a simple function to encapsulate the behavior, but it not already existing in the standard library suggests that I may be thinking about the scenario wrong.

import Data.Char

isLit :: String -> Bool
isLit = isDigit . head

takePiece :: String -> (String,String)
takePiece str
    | isLit str = break (not . isDigit) str
    | otherwise = splitAt 1 str

cutEqu :: String -> [String]
cutEqu [] = []
cutEqu xs = let (p,rest) = takePiece xs in
            p : cutEqu rest

Edit: Here's my attempt at writing it implicitly:

consumeWith :: ([a] -> ([b],[a])) -> [a] -> [[b]]
consumeWith _ [] = []
consumeWith f xs = let (t, rest) = f xs in
    t : consumeWith f rest

cutEqu' :: String -> [String]
cutEqu' = consumeWith (takePiece)

But again, I'm concerned that anything like this isn't a standard function. Is there a better way of going about this?

Upvotes: 3

Views: 283

Answers (2)

Luis Casillas
Luis Casillas

Reputation: 30227

I don't think implicit vs. explicit recursion is the issue you should focus on here. The first thing I'd advise you to do is to split this problem into two parts:

  1. Parsing: Take the string and produce an abstract syntax tree ("AST") that represents the formula.
  2. Evaluation: Take the AST and produce the result.

I can't tell from your code what is the structure of the equation language you're trying to implement here. This is the place I'd start, not the parsing: defining the data type for the AST. For example, here is an AST suitable for a simple expression language with variables, numeric literals, addition, subtraction and multiplication:

import Control.Applicative (liftA2)
import Data.Map (Map)
import qualified Data.Map as Map

-- | The abstract syntax tree for the expression language.
data Expr a = Var String
            | Lit a
            | Add (Expr a) (Expr a)
            | Sub (Expr a) (Expr a)
            | Mul (Expr a) (Expr a)
    deriving Show


-- | Evaluate an 'Expr', using a 'Map' of variable names to values to represent the
-- evaluation environment.
eval :: Num a => Map String a -> Expr a -> Maybe a
eval env (Var v) = Map.lookup v env
eval env (Lit a) = Just a
eval env (Add expr1 expr2) = liftA2 (+) (eval env expr1) (eval env expr2)
eval env (Sub expr1 expr2) = liftA2 (-) (eval env expr1) (eval env expr2)
eval env (Mul expr1 expr2) = liftA2 (*) (eval env expr1) (eval env expr2)

Then to complete the implementation, you write a function with this signature:

parse :: String -> Maybe Expr

And I'd say that, in fact, explicit recursion on an AST type like Expr is a fine solution for a simple interpreter like this. The "prefer implicit recursion" advice works better for collection types like lists, because it makes code easier to write and read. But in the case of a simple AST-based interpreter, what you want to do is define the AST so that it serve as a scaffolding for writing simple evaluation rules that say how the value of an expression is related to the value of its subexpressions (known as compositionality).

Upvotes: 1

ErikR
ErikR

Reputation: 52029

The pattern is called unfoldr which has the type signature:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Your cutEq function can be written in terms of unfoldr like this:

import Data.List

cutEq' str = unfoldr go str
  where go [] = Nothing
        go xs = Just $ takePiece xs

Upvotes: 5

Related Questions