Would a Declarative Multi-Aspect Fold Be Performant?

Feedback
#1

Just wondering whether this idea already exists somewhere / how performant it would end up being given the usage of row kinds and the need for type-level programming to prove that it’s type-safe.

Let’s say you have the following types:

type Rec =
  { count :: Int
  , name :: String
  , other :: String
  }
type Example = Array Rec

You would like to use to write something like this because of its declarative easy-to-read nature.

getSpecificStuff 
  :: Array Rec 
  -> { maxCount :: Int, maxLength :: Int, value :: List String }
getSpecificStuff arrayRec =
let
 totalCount = sum $ map (_.count) arrayRec
 maxLength = max $ map (length <<< _.name) arrayRec
 allValuesAsList = reverse $ foldl (flip Cons) Nil $ map (_.other) arrayRec
in { totalCount, maxLength, allValuesAsList }

However, you don’t want to iterate through the array multiple times. Rather, you would like to iterate through it once for performance without losing the declarative nature of this code.

So, you write something like this instead:

getSpecificStuff
  :: Array Rec 
  -> { maxCount :: Int, maxLength :: Int, otherList :: List String }
getSpecificStuff =
  buildFoldl
    { totalCount: sumWith (_.count)
    , maxLength: maxWith 0 (length <<< _.name)
    , otherList: {init: Nil, acc: flip Cons }
    }
  where
  sumWith f = { init: zero, acc: \acc next -> acc + (f next) }
  maxWith init f = { init, acc: \acc next -> max acc (f next) }
  buildFoldl 
    :: forall f a.
     . Foldable f
    => ?Some_Definition -> f a -> Record ?OutputRows
  buildFoldl rec foldableThing = 
    -- pseudo code below!
    let 
      result = foldl (\acc next -> ?stuff) rec foldableThing
    in mapLikeFunction (_.acc) result

Assuming it’s even possible to type-check, would buildFoldl even be performant considering all of the type class dictionaries being passed around?

2 Likes
#2

Given getSpecificStuff :: Array Rec -> { maxCount :: Int, maxLength :: Int, value :: List String } you can already do it as a single fold over the input:

type Rec =
  { count :: Int
  , name :: String
  , other :: String
  }

type Example = Array Rec

type Result =
  { maxCount :: Int
  , maxLength :: Int
  , value :: Array String
  }

getSpecificStuff :: Array Rec -> Result
getSpecificStuff = foldl go { maxCount: 0, maxLength: 0, value: [] }
  where
  go { maxCount, maxLength, value } { count, name, other } =
    { maxCount: maxCount + count
    , maxLength: max maxLength (String.length name)
    , value: value <> [other]
    }
1 Like
#3

Ah, true. I guess I was overthinking this. I wanted to be able to write something like that where I can easily add/remove something by only changing one line. The above approach requires me to modify things in multiple places, but anything else likely would be unnecessary overhead.

1 Like
#4

If you formulate it as a Monoidal operation, you get this with foldMap, since a record is a Monoid if it’s fields are. foldMap is a minimal definition of Foldable, so it’s always possible, if potentially inconvenient.

#5

Also see https://github.com/paf31/purescript-folds

1 Like
#6

To answer this specifically, it depends. By “performant” do you mean equivalent to the performance of a hand-written fold? With the current state of things, this is unlikely, at least from the compilers POV. A good inliner could turn everything into the equivalent hand-written fold for sure, but we don’t have that. How an engine’s JIT might optimize it, I couldn’t say.

3 Likes
#7

Thanks for the feedback, thoughts, and links.

1 Like