Implement Grid Search

Implement a grid search function for hyperparameter optimization. Grid search is a technique used to find the optimal set of hyperparameters for a machine learning model by exhaustively searching through all possible combinations of specified parameter values.

Your function should:

1. Accept training data, validation data, a parameter grid (dictionary mapping parameter names to lists of values), a model function, and a scoring function
2. Generate all possible combinations of hyperparameters from the parameter grid
3. Evaluate each combination by training/predicting with the model function and scoring with the scoring function
4. Return the best parameter combination and its corresponding score (rounded to 4 decimal places)

The model_fn signature is: model_fn(X_train, y_train, X_val, **params) -> predictions The scoring_fn signature is: scoring_fn(y_true, y_pred) -> score (higher is better)

When multiple parameter combinations achieve the same best score, return the first one encountered (based on the order of iteration through combinations).

import numpy as np
from itertools import product

def grid_search(X_train: np.ndarray, y_train: np.ndarray, 
                X_val: np.ndarray, y_val: np.ndarray,
                param_grid: dict, model_fn: callable, 
                scoring_fn: callable) -> tuple:
    """
    Perform grid search to find optimal hyperparameters.
    
    Args:
        X_train: Training features
        y_train: Training labels  
        X_val: Validation features
        y_val: Validation labels
        param_grid: Dict mapping parameter names to lists of values to try
        model_fn: Function(X_train, y_train, X_val, **params) -> predictions
        scoring_fn: Function(y_true, y_pred) -> score (higher is better)
    
    Returns:
        Tuple of (best_params dict, best_score rounded to 4 decimals)
    """
    pass