How can I write this as an implicit recursion?
I am trying to write a module that can take the string representation of a simple equation and evaluate it. As a first step, I need to translate the equation into separate tokens; based on "rules" takePiece
. I tried writing cutEqu
as a fold, but I ran into a problem that I really don't fold over the line; I take on a different size until it runs out. I could trick and make it collapse over a list of numbers equal to the length of the string, but that seems awkward.
In most of the tutorials I've read, they point out that explicit recursion is a rare occurrence when you understand implicit recursive patterns (like folds and maps) and it looks like a potentially common scenario, but can't find an appropriate standard function to handle it ... How can someone write something as simple as cutEqu
using implicit recursion? I'm sure I can find a simple function to encapsulate the behavior, but it doesn't exist in the standard library yet, so I might be thinking of a wrong scenario.
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 am concerned that something like this is not a standard function. Is there a better way to do this?
source to share
I don't think the implied vs. explicit recursion is a problem you should focus on. The first thing I will advise you is to split this problem into two parts:
- Parse: Take a string and create an abstract syntax tree ("AST") that represents the formula.
- Assessment: Take AST and get results.
I cannot tell from your code what is the structure of the equation language you are trying to implement here. This is the place I would start, not parsing: defining a datatype for an AST. For example, here ANT is suitable for a simple language of expression 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 would say that in fact, explicit recursion by AST type Expr
is a fine solution for a simple interpreter like this. The "prefer implicit recursion" guidelines work better for collection types such as lists because it makes the 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 serves as a forest for writing simple evaluation rules that say how the value of an expression relates to the value of its subexpressions (known as compositionality ).
source to share