Functional Programming Questions

Risks

• unsafePerformIO breaks purity: unpredictable ordering, compiler optimizations may elide or duplicate IO, causing subtle bugs or memory leaks.
• Partial functions (fromJust, head, etc.) can crash at runtime; they hide precondition failures and make reasoning and refactoring unsafe.
• Combined: cached value via unsafePerformIO + partials → hard-to-reproduce crashes and non-deterministic behavior.

Refactor approach (concrete)

1. Remove unsafePerformIO by making caching explicit via IORef/MVar or a pure memoization structure passed through context.

• Replace:

{-# NOINLINE cached #-}
cached :: Foo
cached = unsafePerformIO $ computeExpensive

• With:

-- initialize once at startup
initCache :: IO (IORef (Maybe Foo))
initCache = newIORef Nothing

getFoo :: IORef (Maybe Foo) -> IO Foo
getFoo ref = do
  m <- readIORef ref
  case m of
    Just v  -> return v
    Nothing -> do
      v <- computeExpensive
      writeIORef ref (Just v)
      return v

2. Eliminate partials: replace fromJust :: Maybe a -> a with total functions that handle Nothing explicitly or propagate Maybe/Either.

• Instead of fromJust (lookup k m), use:

case Map.lookup k m of
  Just v -> v
  Nothing -> throwIO (userError $ "missing key: " ++ show k)
-- or return Either/Error upstream

3. Dependency injection: pass cache handle or ReaderT env so code remains testable and pure where possible.

Testing the refactor

• Unit tests: verify behavior for present and missing keys; assert no exceptions for normal paths and specific errors for absent data.
• Property tests (QuickCheck): idempotence of getFoo (multiple calls return same result), thread-safety by running concurrent callers (use HUnit + Control.Concurrent for race checks).
• Integration tests: substitute a fake computeExpensive to count invocations—ensure caching calls computeExpensive once.
• Fuzz tests: feed malformed inputs to ensure Nothing paths handled.

Why this is better

• Restores referential transparency, easier reasoning, safer compiler optimizations.
• Explicit error handling surfaces contracts and makes maintenance safer.
• DI + explicit IO boundaries improve testability and concurrency safety.

Approach: define a Serializable typeclass that encodes to ByteString and decodes with error reporting. Use Data.ByteString and Data.ByteString.Builder for efficient binary encoding and Data.Binary.Get for parsing. Provide instances for Int (as 64-bit big-endian) and Maybe a (tagged). Discuss versioning by adding version tags to the serialized form and providing helper methods for version-aware parsing and migration.

{-# LANGUAGE FlexibleContexts, FlexibleInstances #-}

import Data.ByteString (ByteString)
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as B
import qualified Data.ByteString.Lazy as L
import Data.Int (Int64)
import Data.Binary.Get
import Data.Binary.Put (putInt64be)
import Data.Binary.Put (runPut)
import Data.Word (Word8)
import Control.Applicative ((<|>))

class Serializable a where
  serialize :: a -> ByteString
  deserialize :: ByteString -> Either String a

-- Int instance: encode as big-endian 8-byte integer
instance Serializable Int where
  serialize i = L.toStrict $ B.toLazyByteString (B.int64BE (fromIntegral i))
  deserialize bs =
    case runGetOrFail getInt64be (L.fromStrict bs) of
      Left (_,_,e) -> Left e
      Right (_,_,v) -> Right (fromIntegral v)

-- Maybe instance: 0x00 = Nothing, 0x01 ++ payload = Just
instance Serializable a => Serializable (Maybe a) where
  serialize Nothing  = BS.singleton 0x00
  serialize (Just x) = BS.cons 0x01 (serialize x)

  deserialize bs = case BS.uncons bs of
    Nothing -> Left "empty input for Maybe"
    Just (tag, rest) -> case tag of
      0x00 -> Right Nothing
      0x01 -> case deserialize rest of
                Left e -> Left ("Maybe inner: " ++ e)
                Right v -> Right (Just v)
      _ -> Left ("Unknown Maybe tag: " ++ show tag)

-- helper Get for Int64
getInt64be :: Get Int64
getInt64be = fromIntegral <$> getInt64be' where
  getInt64be' = do
    -- use built-in
    getInt64be

Key points:

• Tagged encoding for Maybe avoids ambiguity.
• Use fixed-width encoding for Int to avoid locale issues.
• deserialize returns Either String for clear error messages.

Versioning & backward compatibility (typeclass-level strategies):

• Include a version tag in the serialized bytes (e.g., first byte or varint). Change deserialize to check version and dispatch to the appropriate parser or migration path.
• Add default methods: serializeV :: Int -> a -> ByteString and deserializeV :: ByteString -> Either String (Int, a) so instances can implement version-aware logic with fallbacks.
• Provide migration functions: fromVersionN :: ByteString -> Either String a to convert old formats to current representation.
• Maintain compatibility by:
  • Using additive changes (new optional fields) with tags.
  • Using union/tagged formats so unknown tags can be skipped.
  • Providing explicit migration code in instances when schema changes.
    Trade-offs:
• Embedding versions increases bytes but enables safe evolution.
• For complex types consider using a schema language (e.g., protobuf/avro) or deriving libraries to automate migrations.

Start with goals and constraints:

• Goal: separate pure business logic from effects so logic is testable, composable, and refactorable.
• Constraint: large legacy codebase with many IO-bound functions; need incremental, low-risk migration and backward compatibility.

High-level architecture proposal:

• Introduce a pure core expressed as abstract algebras (typeclasses) — tagless-final style — or as a Free Monad/Freer for more runtime inspection. I recommend tagless-final for ergonomics and performance; Free if you need to serialize or visualize programs.
• Keep thin effectful entry points (main, HTTP handlers, CLI) which assemble interpreters and run the pure programs by providing concrete IO interpreters.

Minimal tagless-final example:

{-# LANGUAGE RankNTypes #-}
class Monad m => UserRepo m where
  getUser :: UserId -> m (Maybe User)
  saveUser :: User -> m ()

-- Pure business logic parameterized over the algebra
createOrUpdateUser :: (Monad m, UserRepo m) => User -> m ()
createOrUpdateUser u = do
  mu <- getUser (userId u)
  case mu of
    Nothing -> saveUser u
    Just _  -> saveUser (u { updated = nowStub })

Concrete IO interpreter lives separately:

newtype DbIO a = DbIO { runDbIO :: IO a }
instance UserRepo DbIO where
  getUser = -- real DB call
  saveUser = -- real DB call

Migration steps (incremental):

1. Identify hot spots: modules with heavy logic + IO. Start with ones with high test value and low dependencies.
2. Extract pure functions inside IO actions: find "pure core" within IO by moving computations that don't touch IO into new pure functions.
3. Introduce small algebras for external concerns (Repo, Clock, Random, HttpClient). Keep them minimal (single responsibility).
4. Rewire functions to accept these algebras (typeclass constraint or explicit record of functions). Prefer typeclasses for tagless-final ergonomics.
5. Implement test interpreters (in-memory maps, deterministic clocks) and unit-test the pure core thoroughly.
6. Replace callers incrementally: for each module, swap direct IO calls with calls to the pure core plus interpreter wiring in outer layers.
7. Continuously run integration tests; maintain compatibility by keeping old IO entry points until full migration.

Testing strategy:

• Unit tests: use pure core with test interpreters -> deterministic, fast.
• Property tests: QuickCheck on pure functions.
• Integration tests: run programs with real IO interpreters in CI (containerized DB).
• Golden tests: capture end-to-end behavior while migrating.

Backward compatibility & risk mitigation:

• Preserve public IO functions as thin adapters that call the new core; mark them deprecated and log usage.
• Use feature flags/branch-by-abstraction for toggling between old and new implementations.
• Incremental releases per module; keep both implementations behind the same API until confidence is high.

Trade-offs:

• Tagless-final: compile-time abstraction, better performance, harder to mock if you used concrete records; but test interpreters are straightforward.
• Free monads: easier to inspect/transform programs, slightly more runtime overhead and boilerplate.

Operational notes:

• Keep algebras small and composable to avoid explosion of typeclass contexts.
• Use effect composition (mtl-style or fused-effects) only when team is comfortable.
• Automate migration with linting rules to detect remaining direct IO usage where business logic should be pure.

This approach produces a small, well-tested pure core and minimal effectful shell, enabling safer refactors, easier testing, and gradual rollout with clear rollback paths.

Approach: implement a small recursive-descent parser with three levels reflecting precedence:

• expr: handles addition (lowest precedence)
• term: handles multiplication (higher precedence)
• factor: integer or parenthesized expression (highest)

This uses Megaparsec and parses directly to Int by folding operators; multiplication is handled in term so it binds tighter than addition.

{-# LANGUAGE OverloadedStrings #-}
import Data.Void (Void)
import Text.Megaparsec
import Text.Megaparsec.Char
import Control.Monad (void)
import Control.Monad.Combinators (chainl1)
import qualified Text.Megaparsec.Char.Lexer as L

type Parser = Parsec Void String

-- Lexing helpers
sc :: Parser ()
sc = L.space space1 (L.skipLineComment "//") empty

lexeme :: Parser a -> Parser a
lexeme = L.lexeme sc

symbol :: String -> Parser String
symbol = L.symbol sc

integer :: Parser Int
integer = lexeme (L.signed sc (fromInteger <$> L.decimal))

-- factor: integer or parenthesized expr
factor :: Parser Int
factor =  integer
      <|> between (symbol "(") (symbol ")") expr

-- term: handles multiplication, higher precedence than addition
term :: Parser Int
term = chainl1 factor mulOp
  where mulOp = do { void (symbol "*"); return (*) }

-- expr: handles addition (lowest precedence)
expr :: Parser Int
expr = chainl1 term addOp
  where addOp = do { void (symbol "+"); return (+) }

-- top-level parse
parseExpr :: String -> Either (ParseErrorBundle String Void) Int
parseExpr = parse (sc *> expr <* eof) ""

-- Example:
-- parseExpr "2 + 3 * (4 + 1)"  => Right 17

Key points:

• Precedence: factor -> term -> expr ensures * binds tighter than + because multiplication is resolved within term before additions in expr.
• chainl1 builds left-associative binary operations (e.g., "a - b - c" would be (a - b) - c; here used for + and *).
• The parser returns Int directly; alternatively you could build an AST and evaluate separately for clarity or extensibility.
• Edge cases: whitespace handled via sc; signed integers supported; invalid input returns a helpful ParseErrorBundle.

Requirements:

• Small embedded DSL for logging with operations: info :: String, debug :: String, and lift of pure values.
• Compare Free Monad vs Tagless-Final on interpreters, performance, type safety, testability.

Free Monad approach — explanation + pros/cons:

• Easy to build AST, multiple interpreters, simple to inspect/transform, good for batching, replay, serialization.
• Interpreter-writing requires pattern matching / fold over AST; can be less efficient (heap/boxing, many small allocations), and monomorphic AST loses some static constraints unless GADTs used.
• Testability: easy to write pure interpreter that records events.

Example Free DSL:

{-# LANGUAGE DeriveFunctor #-}
data LogF next = Info String next | Debug String next deriving Functor
type FreeLog = Free LogF

info :: String -> FreeLog ()
info msg = liftF (Info msg ())
debug :: String -> FreeLog ()
debug msg = liftF (Debug msg ())
-- interpreter to IO
runIO :: FreeLog a -> IO a
runIO = iterM alg where
  alg (Info s k) = putStrLn ("INFO: "++s) >> k
  alg (Debug s k)= putStrLn ("DEBUG: "++s) >> k

Tagless-Final approach — explanation + pros/cons:

• Define an interface (typeclass) describing operations parametrized by effect type m. Each interpreter is an instance. No intermediate AST; zero-cost abstraction after optimization, better performance and easier to compose with typeclass-based constraints (Monad, MonadIO).
• Harder to inspect or transform programs; capturing/serializing programs requires more work (free-like representation or effects library).
• Testability: mock interpreters as instances that, e.g., accumulate messages in Writer.

Example Tagless-Final DSL:

class Monad m => MonadLog m where
  info :: String -> m ()
  debug :: String -> m ()

-- IO interpreter
instance MonadLog IO where
  info s = putStrLn ("INFO: "++s)
  debug s = putStrLn ("DEBUG: "++s)

-- pure test interpreter
newtype TestM a = TestM { runTestM :: Writer [String] a } deriving (Functor, Applicative, Monad)
instance MonadLog TestM where
  info s = tell ["INFO: "++s]
  debug s = tell ["DEBUG: "++s]

Trade-offs summary:

• Ease of defining interpreters: Free — pattern-match/fold; Tagless — implement instances (both straightforward).
• Performance: Tagless-Final usually faster (no AST allocation), better inlined; Free has overhead unless optimized.
• Type safety: Both type-safe; Tagless-Final allows richer typeclass constraints and more precise effect typing; Free can be extended with GADTs for richer invariants.
• Testability & tooling: Free excels at inspection, transformation, replay and serialization; Tagless-Final excels at lightweight testing via mock instances and integrates naturally with other effects.

When to choose:

• Use Free when you need program introspection, replay, persistence, or many different interpreters and transformations.
• Use Tagless-Final when performance and composability with other typeclass-based effects matter and you don't need to manipulate an explicit AST.