Реализовать функционал карты для списка списков без использования вложенных карт

Question

Я поставил перед собой следующий вызов (и не смог):

Я хочу написать функционал карты map f lofls, который принимает функцию f 'a -> 'b и список списков lofls 'a list list и применяет функцию f к каждому элементу списка списков. Ограничение, которое я добавил, заключается в том, что мне не разрешено использовать вложенные карты для списков, и я должен делать это рекурсивно.

Я пытался сделать это на F #, но любой язык должен это делать. Есть идеи?

Редактировать

Вот моя попытка (которая работает, но уродлива, и я тоже не фанат использования rev ...)

let map f lis = 
    let rec map2 f lis aux =
        match (lis, aux) with
        |([], []) -> []
        |([], aux) -> [aux]
        |(hd::tl, aux) ->
            match hd with 
            |[] -> (List.rev aux) :: (map2 f tl [])
            |x::xs -> map2 f (xs::tl) ( (f x) :: aux )
    map2 f lis []

(я также понял, что это уже было опубликовано в более краткой форме)

Answer 1

Я не уверен, почему этот вопрос помечен с помощью SML, но поскольку это так, вот как это можно сделать в SML:

Во-первых, это идиоматическое решение, которое вы явно избегаете:

fun mapmap f = map (map f)

(Вы могли бы написать val mapmap = map o map, если бы не ограничение значения ML .)

И если вы 'Я хотел бы написать mapmap, используя явную рекурсию:

fun mapmap f [] = []
  | mapmap f (xs::xss) = map f xs :: mapmap f xss

and map f [] = []
  | map f (x::xs) = f x :: map f xs

Одна из причин, почему эту функцию трудно написать с помощью одной явно рекурсивной функции, заключается в том, что стек вызовов используется для двух вещей:

1. Сбор результатов каждого внутреннего списка и
2. Сбор результатов внешнего списка.

Одно из этих применений стека вызовов можно превратить вявный стек в аккумулирующем аргументе.Вот как, например, определяется хвостовая рекурсия rev:

fun rev xs =
  let fun aux [] acc = acc
        | aux (x::xs) acc = aux xs (x::acc)
  in aux xs [] end

Аргумент накопления аналогично не нужен в интерфейсе к mapmap, поэтому он может быть скрыт во внутренней вспомогательной функции.Таким образом, единственная функция, которая выполняет явную рекурсию как во внутреннем, так и во внешнем списке, усложняется этой явной бухгалтерией:

fun mapmap f xss =
  let fun aux f [] _ = []
        | aux f ([]::xss) ys = rev ys :: aux f xss []
        | aux f ((x::xs)::xss) ys = aux f (xs::xss) (f x :: ys)
  in aux f xss [] end

Answer 2

Если бы это был домашний вопрос, а я уверен, что это не так, ответ зависит от того, что составляет «вложенную карту для списков».

Конструкцию, подобную map [] (map [] f), можно переписать с конвейерной обработкой как f |> map [] |> map [] или оператором композиции функций как (map [] >> map []) f, но ее все равно можно считать вложенной картой.

let mapNested f =
    let rec map acc g = function
    | [] -> List.rev acc
    | x::xs -> map (g x::acc) g xs
    f |> map [] |> map [] 
// val mapNested : f:('a -> 'b) -> ('a list list -> 'b list list)

Это возможность продемонстрировать ваше понимание лямбда-исчисления и комбинатора Y . Вложенная передача функции map в качестве аргумента должна явно проходить проверку.

let rec Y f x = f (Y f) x

let map f acc g = function
| [] -> List.rev acc
| x::xs -> f (g x::acc) g xs

let map1 f =
    Y map [] f
// val map1 : f:('a -> 'b) -> ('a list -> 'b list)

let map2 f =
    Y map [] f
    |> Y map []
// val map2 : f:('a -> 'b) -> ('a list list -> 'b list list)

Answer 3

Другой способ:

let rec mapNested f lofls =
    match lofls with
    | []   -> []
    | h::t -> (map f h) :: (mapNested f t)
and map f lst = 
    match lst with
    | []   -> []
    | h::t -> (f h) :: (map f t)

Answer 4

Хвост рекурсивным способом

let mapNested f lofls =
    let rec map f lst acc =
        match lst with
        | []   -> List.rev acc
        | h::t -> map f t (f h :: acc)
    map (fun x -> map f x []) lofls []

Answer 5

Давайте пошагово, от простого к сложному.

Это подпись, которую вы хотите, чтобы ваша функция map имела:

('a -> 'b) -> 'a list list -> 'b list list

Простое решение таково:

let map0 (f:'a -> 'b) (lofls:'a list list) : 'b list list = lofls |> List.map (List.map f)

Но этот не является рекурсивным и использует вложенные карты.

Рекурсивное решение может быть таким:

let rec map1 (f:'a -> 'b) (lofls:'a list list) : 'b list list =
    match lofls with
    | []      -> []
    | l::rest -> (List.map f l) :: map1 f rest

Он рекурсивный, хотя он все еще вызывает там List.map.

Итак, вот следующий уровень:

let rec map (f:'a -> 'b) (lofls:'a list list) : 'b list list =
    match  lofls                    with
    | [          ]         -> [              ]
    | [          ] :: rest -> [              ] :: (rest |> map f)
    | ( e::restl ) :: rest -> 
    match  restl   :: rest |> map f with
    | [          ]         -> [              ]
    | [          ] :: rest -> [ f e          ] ::  rest
    | (    restl ) :: rest -> ( f e :: restl ) ::  rest