haskell_eval.hs

import Debug.Trace -- Optional: for debugging if needed, remove in final version

data Bits = O Bits | I Bits | E deriving (Show, Eq)

-- Helper function to append two Bits sequences.
-- append xs ys concatenates xs and ys.
append :: Bits -> Bits -> Bits
append E ys = ys
append (O xs) ys = O (append xs ys)
append (I xs) ys = I (append xs ys)

-- Helper function to parse one <Uint> from the beginning of a Bits sequence.
-- It returns a tuple: (parsed <Uint>, remaining Bits sequence).
-- Assumes the input sequence starts with a valid <Uint>.
parseUint :: Bits -> (Bits, Bits)
parseUint (O rest) = (O E, rest) -- Uint is 0 ('O E'), rest is the remainder
parseUint (I inner) = 
  -- Uint starts with '1'. Recursively parse the inner part.
  let (parsedInnerUint, actualRest) = parseUint inner 
  -- The full Uint is '1' prepended to the parsed inner Uint.
  in (I parsedInnerUint, actualRest)
-- parseUint E should not happen for valid inputs according to the grammar.
parseUint E = error "parseUint encountered E, invalid format for <Uint>"

-- The main function 'f'. Renamed to 'fn' as requested.
-- fn N XS: sets the Nth (0-indexed) element of the list XS to 0.
-- N is a <Uint> representing the index.
-- XS is a <List> representing the list of <Uint>s.
fn :: Bits -> Bits -> Bits
-- Base case 1: If the list XS is empty ('O E'), we cannot modify anything. Return empty list.
fn _ (O E) = O E

-- Base case 2: If XS is 'E', it's an invalid list format (should end with 'O E').
fn _ E = error "fn encountered E in list structure, invalid format for <List>"

-- Recursive step: The list XS is non-empty, represented as 'I <Uint> <ListTail>'.
-- 'rest' here represents the sequence "<Uint> <ListTail>".
fn n (I rest) =
  -- Parse the first element (<Uint>) and the rest of the list (<ListTail>) from 'rest'.
  let (currentUint, listTail) = parseUint rest
  in case n of
       -- Case 1: The index N is 0 ('O E'). We've found the element to modify.
       O E ->
         -- Replace the currentUint with 0 ('O E').
         -- Reconstruct the list: 'I' followed by <Uint=0> followed by <ListTail>.
         -- We use append to concatenate <Uint=0> and <ListTail>.
         I (append (O E) listTail)

       -- Case 2: The index N is greater than 0 ('I n_decrement').
       I n_decrement ->
         -- We need to modify an element further down the list.
         -- Keep the currentUint as it is.
         -- Recursively call fn on the rest of the list (<ListTail>) with the decremented index (n_decrement).
         let modifiedTail = fn n_decrement listTail
         -- Reconstruct the list: 'I' followed by the original currentUint followed by the modifiedTail.
         in I (append currentUint modifiedTail)

       -- Case 3: N is 'E'. This is an invalid format for a <Uint> index.
       E -> error "fn encountered E as index N, invalid format for <Uint>"

-- SOLUTION HERE - The implementation is above.

main :: IO ()
main = do
  -- Test case 1: fn 2 [1,2,3] should be [1,2,0]
  -- N = 2  is 110 which is I (I (O E))
  -- XS = [1,2,3] is '1 10 1 110 1 1110 0'
  -- XS = I (I (O (I (I (I (O (I (I (I (I (O (O E))))))))))))
  let x0 = fn (I (I (O E))) (I (I (O (I (I (I (O (I (I (I (I (O (O E)))))))))))))
  -- Expected YS = [1,2,0] is '1 10 1 110 1 0 0'
  -- YS = I (I (O (I (I (I (O (I (O (O E)))))))))
  let y0 = I (I (O (I (I (I (O (I (O (O E)))))))))
  
  -- Test case 2: fn 2 [0,0,0] should be [0,0,0]
  -- N = 2 is 110 which is I (I (O E))
  -- XS = [0,0,0] is '1 0 1 0 1 0 0'
  -- XS = I (O (I (O (I (O (O E))))))
  let x1 = fn (I (I (O E))) (I (O (I (O (I (O (O E)))))))
  -- Expected YS = [0,0,0] is '1 0 1 0 1 0 0'
  -- YS = I (O (I (O (I (O (O E))))))
  let y1 = I (O (I (O (I (O (O E))))))
  
  -- Check if results match expected values
  putStrLn $ "Test 1 Passed: " ++ show (x0 == y0)
  putStrLn $ "Test 2 Passed: " ++ show (x1 == y1)
  print $ x0 == y0 && x1 == y1