Сложите это как постоянное пространство и короткое замыкание - PullRequest
Новая
       25

Сложите это как постоянное пространство и короткое замыкание

3 голосов
/ 14 марта 2019

Я пытаюсь создать функцию на Haskell, которая делает в основном то же самое, что и * Pre 100 *. Однако, в отличие от этой функции, она должна иметь следующие два свойства:

  1. Он должен работать в постоянном пространстве (игнорируя тот факт, что некоторые числовые типы, такие как Integer, не являются). Например, я хочу, чтобы myProduct (replicate 100000000 1) в конечном итоге вернул 1, в отличие от product Prelude, который использует всю мою оперативную память и затем выдает *** Exception: stack overflow.
  2. Он должен закорачиваться, когда встречается с 0. Например, я хочу, чтобы myProduct (0:undefined) возвращал 0, в отличие от product Prelude, который дает *** Exception: Prelude.undefined.

Вот что я придумала до сих пор: 

myProduct :: (Eq n, Num n) => [n] -> n
myProduct = go 1
  where go acc (x:xs) = if x == 0 then 0 else acc `seq` go (acc * x) xs
        go acc []     = acc

Это работает именно так, как я хочу, чтобы списки, но я хотел бы обобщить, чтобы иметь тип (Foldable t, Eq n, Num n) => t n -> n. Можно ли сделать это с любой из складок? Если я просто использую foldr, то это будет короткое замыкание, но не будет с постоянным пространством, а если я просто использую foldl', то это будет постоянное пространство, но не будет с коротким замыканием.

Ответы [ 2 ]

3 голосов
/ 14 марта 2019

Если вы пишете свою функцию немного по-другому, становится более очевидным, как превратить ее в foldr. А именно: 

myProduct :: (Eq n, Num n) => [n] -> n
myProduct = flip go 1 where
    go (x:xs) = if x == 0 then \acc -> 0 else \acc -> acc `seq` go xs (acc * x)
    go [] = \acc -> acc

Теперь go имеет этот foldr аромат, и мы можем просто заполнить отверстия. 

myProduct :: (Foldable t, Eq n, Num n) => t n -> n
myProduct = flip go 1 where
    go = foldr
        (\x f -> if x == 0 then \acc -> 0 else \acc -> acc `seq` f (acc * x))
        (\acc -> acc)

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

myProduct :: (Foldable t, Eq n, Num n) => t n -> n
myProduct xs = foldr step id xs 1 where
    step 0 f acc = 0
    step x f acc = f $! acc * x

И мы все сделали! Небольшое быстрое тестирование в ghci показывает, что оно все еще замыкается на 0 по мере необходимости и использует постоянный пробел.

2 голосов
/ 14 марта 2019

Возможно, вы ищете foldM. Создайте его с помощью m = Either b, и вы получите поведение при коротком замыкании (или Maybe, зависит от того, имеется ли у вас много возможных значений раннего выхода или одно из известных заранее). 

foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

Я вспоминаю дискуссии о том, должно ли быть foldM', но IIRC GHC большую часть времени поступает правильно. 

import Control.Monad
import Data.Maybe

myProduct :: (Foldable t, Eq n, Num n) => t n -> n
myProduct = fromMaybe 0 . foldM go 1
  where go acc x = if x == 0 then Nothing else Just $! acc * x
...