Lazy filter with multi param function in haskell

Question

Я пишу функцию, которая удаляет пустое пространство в строке json. I необходимо знать, находится ли текущий обработчик, обработанный мной, ", или , если это после побега char \. Поэтому мне нужно еще два параметра для этой функции .

Вот текущая реализация. Но я не думаю, что это лениво. Как я мог сделать это ленивым с помощью «фильтра» или «карты» на строку json?

compressJson :: String -> String 
compressJson json = compress json False False "" 
    -- compress params: json, inStr, aferEscape, acc 
    where compress []   _  _  acc = acc 
      compress ('\"' : xs) inStr False acc = compress xs (not inStr) False (acC++ "\"") 
      compress ('\\' : xs) inStr False acc = compress xs inStr  True acc 
      compress (x : xs) inStr True acc = compress xs inStr  False (acC++ ['\\', x]) 
      compress (x : xs) True False acc = compress xs True  False (acC++ [x]) 
      compress (x : xs) False _  acc = compress xs False  False (acC++ parse x) 

      parse c = if c `elem` " \t\n" 
       then [] 
       else [c] 

Answer 1

Это фактически тривиально, чтобы сделать ленивым - не делайте его хвостовым рекурсивным.

Более или менее, как это (я не проверял)

compressJson :: String -> String 
compressJson json = compress json False False 
    -- compress params: json, inStr, aferEscape 
    where compress []   _  _  = "" 
      compress ('\"' : xs) inStr False = '\"' : compress xs (not inStr) False 
      compress ('\\' : xs) inStr False = compress xs inStr True 
      compress (x : xs) inStr True = '\\' : x : compress xs inStr False 
      compress (x : xs) True False = x : compress xs True False 
      compress (x : xs) False _  = parse x ++ compress xs False False 

      parse c = if c `elem` " \t\n" 
       then [] 
       else [c] 

Хвостовая рекурсия и лень на прямые конфликтуют друг с другом. Рекурсия хвоста подразумевает, что функция представляет собой вызов для себя с измененными параметрами. Лень подразумевает, что он быстро возвращает конструктор (т. Е. Не после некоторого неопределенного количества рекурсивных вызовов). Поэтому, если вы хотите, чтобы функция была ленивой, напишите ее, чтобы немедленно вернуть частичные результаты.

Answer 2

Слово «ленивый» в вопросе означает, что нам нужна функция, которая «наименее вынуждает на входе и наиболее продуктивна на выходе». То же слово используется в «ленивой оценке» Хаскелла, так что это может сбивать с толку.

Производственные функции могут быть закодированы с охраняемой рекурсией, как в Carl's great answer. Это следует за рисунком foldr w.r.t. входная строка, но foldl w.r.t. другие 2 параметра. Другими словами, он строит свой вывод справа налево, но для этого ему нужно передать контрольные параметры слева направо. Следовательно, вопрос OP о том, как кодировать это с помощью HOF (), делает его ленивым с filter или map ... ").

Охраняемая рекурсия тесно связана с corecursion. Corecursion, в основном, разворачивается. Рекурсия «возвращается», но кокуркация «идет вперед». Постепенное потребление ввода поэтапно можно рассматривать как «движение вперед» вдоль него. Таким образом, мы будем использовать unfoldr и потребляем его выход с concat (чтобы удовлетворить необходимость пропуска или иногда производить более одного элемента на выходе).

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

import Data.List (unfoldr) 

compressJson :: String -> String 
compressJson json = -- g json False False "" 
        concat $ unfoldr h (json,False,False) 
    where 
    {- g params: json, inStr, aferEscape, acc 
    g []   _  _  acc = acc 
    g ('\"' : xs) inStr False acc = g xs (not inStr) False (acC++ "\"") 
    g ('\\' : xs) inStr False acc = g xs inStr  True acc 
    g (x : xs) inStr True acc = g xs inStr  False (acC++ ['\\', x]) 
    g (x : xs) True False acc = g xs True  False (acC++ [x]) 
    g (x : xs) False _  acc = g xs False  False (acC++ parse x) 
    -} 
    parse c = [c | not (c `elem` " \t\n")] 

    h ([]  , _ , _ ) = Nothing 
    h ('\"' : xs, inStr, False) = Just ("\"",  (xs, not inStr, False)) 
    h ('\\' : xs, inStr, False) = Just ([] ,  (xs,  inStr, True)) 
    h (x : xs, inStr, True) = Just (['\\', x],(xs,  inStr, False)) 
    h (x : xs, True , False) = Just ([x],  (xs,  True, False)) 
    h (x : xs, False, _ ) = Just (parse x, (xs,  False, False)) 

Смотри также:

• Prolog Accumulators. Are they really a "different" concept?.

• Technical Report TR19: Unwinding Structured Recursions into Iterations.
  Daniel P. Friedman and David S. Wise (Dec 1974).