Parallel fold

In one of my previous posts about recursive morphisms I end the text with question: how to parallelize it? Consider one of list recursive morphisms application - left folding of lists. Each result depends on previous result and seems like non-paralellizable. It looks like:

foldl($, {a, b, c, d}) = ((a $ b) $ c) $ d

where $ is some abstract operation. But if <$, {a, b, c, d}> is semi-group then we can do next:

Let
    x = a $ b
    y = c $ d
(x $ c) $ d = x $ (c $ d) = x $ y

because $ is associative operation. So, we see that we have 2 sub-expressions: x and y which can be evaluated in parallel: (a $ b) $ (c $ d).

If $ is + it looks like, for example:

foldl(+, {1, 2, 3, 4})

1   2    3   4
  3   ||   7
      10

Can we parallelize more complex expressions (not special related to folding)? For example, a + b - c - d ? Yes. If {a, b, c, d} is group then we can replace any '.. - x' by '.. + (-x)' where (-x) is the opposite element: our parallelized function must do something like this:

if op is not associative:
  op = op-1
  y = -y
  result <- x op y

where op op^-1 = id. Fo sum. groups +^-1 is -, for prod. groups *^-1 is /.

Interval Ariphmetic on free types

I had already post about interval arithmetic, so here is only additional example of 2nd algorithm, based on analizing of sorted edges of the interval:

But now implementation will be in Haskell and shows how to do interval arithmetic with not integers only, but any other type (which can have some metric, i.e. be ordering):

{-# LANGUAGE ExistentialQuantification #-}
import Data.List

data Iv e = Ord e => Iv e e

makeIv e1 e2 =
  Iv e1' e2' where [e1', e2'] = sort [e1, e2]

ivFst (Iv e _) = e
ivSnd (Iv _ e) = e
iv2List (Iv e1 e2) = [e1, e2]

mergeIv :: Ord e => Iv e -> Iv e -> [Iv e]
mergeIv i1 i2 =
  let sx = sort $ (iv2List i1) ++ (iv2List i2)
      [isx1, isx2] = sortBy (\x y->compare (ivSnd x) (ivSnd y)) [i1, i2] in
    case (ivSnd isx1) `compare` (ivFst isx2) of
      LT -> [Iv (sx!!0) (sx!!1), Iv (sx!!2) (sx!!3)]
      _ -> [Iv (sx!!0) (sx!!3)]


-- Examples:
data Color = Red|Orange|Yellow|Green|Blue|Indigo|Violet deriving (Eq, Ord, Show)

main = do
  print $ map iv2List $ mergeIv (makeIv 20 1) (makeIv (-1) 10)
  print $ map iv2List $ mergeIv (makeIv Red Blue) (makeIv Orange Indigo)

You see example with colors: merging of [Red; Blue] interval with [Orange; Indigo] gives us result as [Red; Indigo] interval :-)

dotspacemacs config (Win)

;; -*- mode: emacs-lisp -*-
;; This file is loaded by Spacemacs at startup.
;; It must be stored in your home directory.

(defun dotspacemacs/layers ()
  "Configuration Layers declaration.
You should not put any user code in this function besides modifying the variable
values."
  (setq-default
   ;; Base distribution to use. This is a layer contained in the directory
   ;; `+distribution'. For now available distributions are `spacemacs-base'
   ;; or `spacemacs'. (default 'spacemacs)
   dotspacemacs-distribution 'spacemacs
   ;; Lazy installation of layers (i.e. layers are installed only when a file
   ;; with a supported type is opened). Possible values are `all', `unused'
   ;; and `nil'. `unused' will lazy install only unused layers (i.e. layers
   ;; not listed in variable `dotspacemacs-configuration-layers'), `all' will
   ;; lazy install any layer that support lazy installation even the layers
   ;; listed in `dotspacemacs-configuration-layers'. `nil' disable the lazy
   ;; installation feature and you have to explicitly list a layer in the
   ;; variable `dotspacemacs-configuration-layers' to install it.
   ;; (default 'unused)
   dotspacemacs-enable-lazy-installation 'unused
   ;; If non-nil then Spacemacs will ask for confirmation before installing
   ;; a layer lazily. (default t)
   dotspacemacs-ask-for-lazy-installation t
   ;; If non-nil layers with lazy install support are lazy installed.
   ;; List of additional paths where to look for configuration layers.
   ;; Paths must have a trailing slash (i.e. `~/.mycontribs/')
   dotspacemacs-configuration-layer-path '()
   ;; List of configuration layers to load.
   dotspacemacs-configuration-layers
   '(
     html
     ;; ----------------------------------------------------------------
     ;; Example of useful layers you may want to use right away.
     ;; Uncomment some layer names and press <SPC f e R> (Vim style) or
     ;; <M-m f e R> (Emacs style) to install them.
     ;; ----------------------------------------------------------------
     helm
     auto-completion
      ;; :variables
      ;; auto-completion-private-snippets-directory "c:/Users/user/AppData/Roaming/.emacs.d/private/snippets"
      ;; auto-completion-enable-snippets-in-popup t)

     ;; better-defaults
     emacs-lisp
     common-lisp
     (haskell :variables haskell-enable-hindent-style "fundamental")
     ;; git
     markdown
     org
     python
     ;; (shell :variables
     ;;        shell-default-height 30
     ;;        shell-default-position 'bottom)
     ;; spell-checking
     ;; syntax-checking
     ;; version-control
     )
   ;; List of additional packages that will be installed without being
   ;; wrapped in a layer. If you need some configuration for these
   ;; packages, then consider creating a layer. You can also put the
   ;; configuration in `dotspacemacs/user-config'.
   dotspacemacs-additional-packages '()
   ;; A list of packages that cannot be updated.
   dotspacemacs-frozen-packages '()
   ;; A list of packages that will not be installed and loaded.
   dotspacemacs-excluded-packages '(evil-unimpaired yasnippet)
   ;; Defines the behaviour of Spacemacs when installing packages.
   ;; Possible values are `used-only', `used-but-keep-unused' and `all'.
   ;; `used-only' installs only explicitly used packages and uninstall any
   ;; unused packages as well as their unused dependencies.
   ;; `used-but-keep-unused' installs only the used packages but won't uninstall
   ;; them if they become unused. `all' installs *all* packages supported by
   ;; Spacemacs and never uninstall them. (default is `used-only')
   dotspacemacs-install-packages 'used-only))

(defun dotspacemacs/init ()
  "Initialization function.
This function is called at the very startup of Spacemacs initialization
before layers configuration.
You should not put any user code in there besides modifying the variable
values."
  ;; This setq-default sexp is an exhaustive list of all the supported
  ;; spacemacs settings.
  (setq-default
   ;; If non nil ELPA repositories are contacted via HTTPS whenever it's
   ;; possible. Set it to nil if you have no way to use HTTPS in your
   ;; environment, otherwise it is strongly recommended to let it set to t.
   ;; This variable has no effect if Emacs is launched with the parameter
   ;; `--insecure' which forces the value of this variable to nil.
   ;; (default t)
   dotspacemacs-elpa-https t
   ;; Maximum allowed time in seconds to contact an ELPA repository.
   dotspacemacs-elpa-timeout 5
   ;; If non nil then spacemacs will check for updates at startup
   ;; when the current branch is not `develop'. Note that checking for
   ;; new versions works via git commands, thus it calls GitHub services
   ;; whenever you start Emacs. (default nil)
   dotspacemacs-check-for-update nil
   ;; If non-nil, a form that evaluates to a package directory. For example, to
   ;; use different package directories for different Emacs versions, set this
   ;; to `emacs-version'.
   dotspacemacs-elpa-subdirectory nil
   ;; One of `vim', `emacs' or `hybrid'.
   ;; `hybrid' is like `vim' except that `insert state' is replaced by the
   ;; `hybrid state' with `emacs' key bindings. The value can also be a list
   ;; with `:variables' keyword (similar to layers). Check the editing styles
   ;; section of the documentation for details on available variables.
   ;; (default 'vim)
   dotspacemacs-editing-style 'vim
   ;; If non nil output loading progress in `*Messages*' buffer. (default nil)
   dotspacemacs-verbose-loading nil
   ;; Specify the startup banner. Default value is `official', it displays
   ;; the official spacemacs logo. An integer value is the index of text
   ;; banner, `random' chooses a random text banner in `core/banners'
   ;; directory. A string value must be a path to an image format supported
   ;; by your Emacs build.
   ;; If the value is nil then no banner is displayed. (default 'official)
   dotspacemacs-startup-banner 'official
   ;; List of items to show in startup buffer or an association list of
   ;; the form `(list-type . list-size)`. If nil then it is disabled.
   ;; Possible values for list-type are:
   ;; `recents' `bookmarks' `projects' `agenda' `todos'."
   ;; List sizes may be nil, in which case
   ;; `spacemacs-buffer-startup-lists-length' takes effect.
   dotspacemacs-startup-lists '((recents . 5)
                                (projects . 7))
   ;; True if the home buffer should respond to resize events.
   dotspacemacs-startup-buffer-responsive t
   ;; Default major mode of the scratch buffer (default `text-mode')
   dotspacemacs-scratch-mode 'text-mode
   ;; List of themes, the first of the list is loaded when spacemacs starts.
   ;; Press <SPC> T n to cycle to the next theme in the list (works great
   ;; with 2 themes variants, one dark and one light)
   dotspacemacs-themes '(spacemacs-dark
                         spacemacs-light)
   ;; If non nil the cursor color matches the state color in GUI Emacs.
   dotspacemacs-colorize-cursor-according-to-state t
   ;; Default font, or prioritized list of fonts. `powerline-scale' allows to
   ;; quickly tweak the mode-line size to make separators look not too crappy.
   dotspacemacs-default-font '("Consolas"
                               :size 24
                               :weight normal
                               :width normal
                               :powerline-scale 1.1)
   ;; The leader key
   dotspacemacs-leader-key "SPC"
   ;; The key used for Emacs commands (M-x) (after pressing on the leader key).
   ;; (default "SPC")
   dotspacemacs-emacs-command-key "SPC"
   ;; The key used for Vim Ex commands (default ":")
   dotspacemacs-ex-command-key ":"
   ;; The leader key accessible in `emacs state' and `insert state'
   ;; (default "M-m")
   dotspacemacs-emacs-leader-key "M-m"
   ;; Major mode leader key is a shortcut key which is the equivalent of
   ;; pressing `<leader> m`. Set it to `nil` to disable it. (default ",")
   dotspacemacs-major-mode-leader-key ","
   ;; Major mode leader key accessible in `emacs state' and `insert state'.
   ;; (default "C-M-m")
   dotspacemacs-major-mode-emacs-leader-key "C-M-m"
   ;; These variables control whether separate commands are bound in the GUI to
   ;; the key pairs C-i, TAB and C-m, RET.
   ;; Setting it to a non-nil value, allows for separate commands under <C-i>
   ;; and TAB or <C-m> and RET.
   ;; In the terminal, these pairs are generally indistinguishable, so this only
   ;; works in the GUI. (default nil)
   dotspacemacs-distinguish-gui-tab nil
   ;; If non nil `Y' is remapped to `y$' in Evil states. (default nil)
   dotspacemacs-remap-Y-to-y$ nil
   ;; If non-nil, the shift mappings `<' and `>' retain visual state if used
   ;; there. (default t)
   dotspacemacs-retain-visual-state-on-shift t
   ;; If non-nil, J and K move lines up and down when in visual mode.
   ;; (default nil)
   dotspacemacs-visual-line-move-text nil
   ;; If non nil, inverse the meaning of `g' in `:substitute' Evil ex-command.
   ;; (default nil)
   dotspacemacs-ex-substitute-global nil
   ;; Name of the default layout (default "Default")
   dotspacemacs-default-layout-name "Default"
   ;; If non nil the default layout name is displayed in the mode-line.
   ;; (default nil)
   dotspacemacs-display-default-layout nil
   ;; If non nil then the last auto saved layouts are resume automatically upon
   ;; start. (default nil)
   dotspacemacs-auto-resume-layouts nil
   ;; Size (in MB) above which spacemacs will prompt to open the large file
   ;; literally to avoid performance issues. Opening a file literally means that
   ;; no major mode or minor modes are active. (default is 1)
   dotspacemacs-large-file-size 1
   ;; Location where to auto-save files. Possible values are `original' to
   ;; auto-save the file in-place, `cache' to auto-save the file to another
   ;; file stored in the cache directory and `nil' to disable auto-saving.
   ;; (default 'cache)
   dotspacemacs-auto-save-file-location 'cache
   ;; Maximum number of rollback slots to keep in the cache. (default 5)
   dotspacemacs-max-rollback-slots 5
   ;; If non nil, `helm' will try to minimize the space it uses. (default nil)
   dotspacemacs-helm-resize nil
   ;; if non nil, the helm header is hidden when there is only one source.
   ;; (default nil)
   dotspacemacs-helm-no-header nil
   ;; define the position to display `helm', options are `bottom', `top',
   ;; `left', or `right'. (default 'bottom)
   dotspacemacs-helm-position 'bottom
   ;; Controls fuzzy matching in helm. If set to `always', force fuzzy matching
   ;; in all non-asynchronous sources. If set to `source', preserve individual
   ;; source settings. Else, disable fuzzy matching in all sources.
   ;; (default 'always)
   dotspacemacs-helm-use-fuzzy 'always
   ;; If non nil the paste micro-state is enabled. When enabled pressing `p`
   ;; several times cycle between the kill ring content. (default nil)
   dotspacemacs-enable-paste-transient-state nil
   ;; Which-key delay in seconds. The which-key buffer is the popup listing
   ;; the commands bound to the current keystroke sequence. (default 0.4)
   dotspacemacs-which-key-delay 0.4
   ;; Which-key frame position. Possible values are `right', `bottom' and
   ;; `right-then-bottom'. right-then-bottom tries to display the frame to the
   ;; right; if there is insufficient space it displays it at the bottom.
   ;; (default 'bottom)
   dotspacemacs-which-key-position 'bottom
   ;; If non nil a progress bar is displayed when spacemacs is loading. This
   ;; may increase the boot time on some systems and emacs builds, set it to
   ;; nil to boost the loading time. (default t)
   dotspacemacs-loading-progress-bar t
   ;; If non nil the frame is fullscreen when Emacs starts up. (default nil)
   ;; (Emacs 24.4+ only)
   dotspacemacs-fullscreen-at-startup nil
   ;; If non nil `spacemacs/toggle-fullscreen' will not use native fullscreen.
   ;; Use to disable fullscreen animations in OSX. (default nil)
   dotspacemacs-fullscreen-use-non-native nil
   ;; If non nil the frame is maximized when Emacs starts up.
   ;; Takes effect only if `dotspacemacs-fullscreen-at-startup' is nil.
   ;; (default nil) (Emacs 24.4+ only)
   dotspacemacs-maximized-at-startup t
   ;; A value from the range (0..100), in increasing opacity, which describes
   ;; the transparency level of a frame when it's active or selected.
   ;; Transparency can be toggled through `toggle-transparency'. (default 90)
   dotspacemacs-active-transparency 90
   ;; A value from the range (0..100), in increasing opacity, which describes
   ;; the transparency level of a frame when it's inactive or deselected.
   ;; Transparency can be toggled through `toggle-transparency'. (default 90)
   dotspacemacs-inactive-transparency 90
   ;; If non nil show the titles of transient states. (default t)
   dotspacemacs-show-transient-state-title t
   ;; If non nil show the color guide hint for transient state keys. (default t)
   dotspacemacs-show-transient-state-color-guide t
   ;; If non nil unicode symbols are displayed in the mode line. (default t)
   dotspacemacs-mode-line-unicode-symbols t
   ;; If non nil smooth scrolling (native-scrolling) is enabled. Smooth
   ;; scrolling overrides the default behavior of Emacs which recenters point
   ;; when it reaches the top or bottom of the screen. (default t)
   dotspacemacs-smooth-scrolling t
   ;; If non nil line numbers are turned on in all `prog-mode' and `text-mode'
   ;; derivatives. If set to `relative', also turns on relative line numbers.
   ;; (default nil)
   dotspacemacs-line-numbers t
   ;; Code folding method. Possible values are `evil' and `origami'.
   ;; (default 'evil)
   dotspacemacs-folding-method 'evil
   ;; If non-nil smartparens-strict-mode will be enabled in programming modes.
   ;; (default nil)
   dotspacemacs-smartparens-strict-mode nil
   ;; If non-nil pressing the closing parenthesis `)' key in insert mode passes
   ;; over any automatically added closing parenthesis, bracket, quote, etc…
   ;; This can be temporary disabled by pressing `C-q' before `)'. (default nil)
   dotspacemacs-smart-closing-parenthesis nil
   ;; Select a scope to highlight delimiters. Possible values are `any',
   ;; `current', `all' or `nil'. Default is `all' (highlight any scope and
   ;; emphasis the current one). (default 'all)
   dotspacemacs-highlight-delimiters 'all
   ;; If non nil, advise quit functions to keep server open when quitting.
   ;; (default nil)
   dotspacemacs-persistent-server nil
   ;; List of search tool executable names. Spacemacs uses the first installed
   ;; tool of the list. Supported tools are `ag', `pt', `ack' and `grep'.
   ;; (default '("ag" "pt" "ack" "grep"))
   dotspacemacs-search-tools '("ag" "pt" "ack" "grep")
   ;; The default package repository used if no explicit repository has been
   ;; specified with an installed package.
   ;; Not used for now. (default nil)
   dotspacemacs-default-package-repository nil
   ;; Delete whitespace while saving buffer. Possible values are `all'
   ;; to aggressively delete empty line and long sequences of whitespace,
   ;; `trailing' to delete only the whitespace at end of lines, `changed'to
   ;; delete only whitespace for changed lines or `nil' to disable cleanup.
   ;; (default nil)
   dotspacemacs-whitespace-cleanup nil
   ))

(defun dotspacemacs/user-init ()
  "Initialization function for user code.
It is called immediately after `dotspacemacs/init', before layer configuration
executes.
 This function is mostly useful for variables that need to be set
before packages are loaded. If you are unsure, you should try in setting them in
`dotspacemacs/user-config' first."
  )

(defun dotspacemacs/user-config ()
  "Configuration function for user code.
This function is called at the very end of Spacemacs initialization after
layers configuration.
This is the place where most of your configurations should be done. Unless it is
explicitly specified that a variable should be set before a package is loaded,
you should place your code here."
  (add-to-list 'exec-path "C:/ccl")
  (add-to-list 'exec-path "C:/python27")
  (setq inferior-lisp-program "wx86cl.exe")
  (setq slime-auto-connect 'ask)
  (setq w32-get-true-file-attributes nil)
  (setq python-shell-interpreter "python")
  (eval-after-load 'flycheck
    '(add-hook 'flycheck-mode-hook #'flycheck-haskell-setup))
  ;; (add-hook 'python-mode-hook (lambda ()
  ;;                               (semantic-mode 1)
  ;;                               (setq flycheck-checker 'python-pylint
  ;;                                     flycheck-checker-error-threshold 900
  ;;                                     flycheck-pylintrc "~/.pylintrc")))

  (setq browse-url-browser-function 'browse-url-generic
        browse-url-generic-program "c:/Links/links-g.exe")
  ;; (setq browse-url-browser-function 'eww-browse-url)

  (setq scroll-step 1) ;; keyboard scroll one line at a time
  ;(require 'sr-speedbar)
  ;(setq sr-speedbar-width 10)
  ;(sr-speedbar-toggle)
  (which-function-mode 1)

  ;(spacemacs/set-leader-keys-for-major-mode 'haskell-mode
  ;    "mht" 'ghc-show-type)
  (setq haskell-indent-spaces 2)
  ;; (setq haskell-process-type 'cabal-repl)

  ;; (setq haskell-process-type 'stack-ghci)
  (setq haskell-process-type 'cabal-repl)
  ;; (setq haskell-process-path-stack "C:/minghc-7.10.2-i386/bin/stack.exe")
  ;; (setq haskell-process-path-ghci "C:/minghc-7.10.2-i386/bin/stack.exe ghci")
  ;; (setq haskell-process-args-ghci '("exec" "ghci"))
  ;; (setq haskell-process-path-cabal "stack.exe exec cabal")
  ;; (setq haskell-process-args-stack-ghci '("--ghc-options=-ferror-spans" "--with-ghc=ghci"))
  (add-hook 'haskell-mode-hook 'inf-haskell-mode)
  (when (configuration-layer/layer-usedp 'haskell)
    (add-hook 'haskell-interactive-mode-hook
              (lambda ()
                (setq-local evil-move-cursor-back t))))
  (add-hook 'haskell-mode-hook 'turn-on-haskell-indentation)
  ;; (eval-after-load 'flycheck '(require 'flycheck-ghcmod))

  (eval-after-load 'org
    '(progn
       (org-babel-do-load-languages
        'org-babel-load-languages
        '((emacs-lisp . t)
          (dot . t)
          (python . t)
          ))
       (setq org-src-fontify-natively t)
       (setq org-src-window-setup 'current-window)
       (setq org-confirm-babel-evaluate nil)
       (setq org-export-with-drawers t)
       (setq org-export-with-section-numbers nil)
       (setq org-export-with-sub-superscripts nil)
       (setq org-export-babel-evaluate nil)
       (setq org-export-backends (quote (ascii html latex md odt rst)))
       ;; (setq org-agenda-files '("~/gtd" "~/gtd/devrel" "~/gtd/mdn" "~/gtd/status.mozmar"))
       (setq org-hide-emphasis-markers t)))

  )

;; Do not write anything past this comment. This is where Emacs will
;; auto-generate custom variable definitions.
(custom-set-variables
 ;; custom-set-variables was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 '(package-selected-packages
   (quote
    (web-mode tagedit slim-mode scss-mode sass-mode pug-mode less-css-mode helm-css-scss haml-mode emmet-mode company-web web-completion-data slime-company slime intero flycheck hlint-refactor hindent helm-hoogle haskell-snippets company-ghci company-ghc ghc haskell-mode company-cabal common-lisp-snippets cmm-mode yapfify smeargle pyvenv pytest pyenv-mode py-isort pip-requirements orgit org-projectile org-present org org-pomodoro alert log4e gntp org-download mmm-mode markdown-toc markdown-mode magit-gitflow live-py-mode hy-mode htmlize helm-pydoc helm-gitignore helm-company helm-c-yasnippet gnuplot gitignore-mode gitconfig-mode gitattributes-mode git-timemachine git-messenger git-link gh-md evil-magit magit magit-popup git-commit with-editor cython-mode company-statistics company-anaconda company auto-yasnippet yasnippet anaconda-mode pythonic ac-ispell auto-complete ws-butler window-numbering which-key volatile-highlights vi-tilde-fringe uuidgen use-package toc-org spaceline powerline restart-emacs request rainbow-delimiters popwin persp-mode pcre2el paradox spinner org-plus-contrib org-bullets open-junk-file neotree move-text macrostep lorem-ipsum linum-relative link-hint info+ indent-guide ido-vertical-mode hydra hungry-delete hl-todo highlight-parentheses highlight-numbers parent-mode highlight-indentation hide-comnt help-fns+ helm-themes helm-swoop helm-projectile helm-mode-manager helm-make projectile pkg-info epl helm-flx helm-descbinds helm-ag google-translate golden-ratio flx-ido flx fill-column-indicator fancy-battery eyebrowse expand-region exec-path-from-shell evil-visualstar evil-visual-mark-mode evil-tutor evil-surround evil-search-highlight-persist evil-numbers evil-nerd-commenter evil-mc evil-matchit evil-lisp-state smartparens evil-indent-plus evil-iedit-state iedit evil-exchange evil-escape evil-ediff evil-args evil-anzu anzu evil goto-chg undo-tree eval-sexp-fu highlight elisp-slime-nav dumb-jump f s diminish define-word column-enforce-mode clean-aindent-mode bind-map bind-key auto-highlight-symbol auto-compile packed dash aggressive-indent adaptive-wrap ace-window ace-link ace-jump-helm-line helm avy helm-core popup async quelpa package-build spacemacs-theme))))
(custom-set-faces
 ;; custom-set-faces was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 )

Catamorphism (with picture:)

Catamorphism is yet another good known recursive scheme which is assitiated with folding. It's simple too and can be shown as pseudocode:

b::B
⊕::A||B->B
h::A*->B

h Nil = b

h([a|as]) = a ⊕ (h as)

This strange operation ⊕ is dyadic operation between list item of type A and "zero"-item of type B.

Scheme graphically looks like:

Some famous functions:

length = CATA<0, ⊕>,  a ⊕ n = 1 + n
map = CATA<Nil, ⊕>,  a ⊕ bs = [f a | bs]

All of these are easy coded in Python:

def cata(b, l, op):
    if not l: return b
    x, *xs = l
    return op(x, cata(b, xs, op))

def length(l):
    return cata(0, l, lambda x, n: 1 + n)

def mymap(f, l):
    return cata([], l, lambda a, bs: [f(a)] + bs)

print(length([1,2,3,4]))
print(mymap(lambda x: x+10, [1,2,3]))

And again: most interesting here is: how to transform it to become parallel.

Anamorphism

Anamorphism is the one of well known recursive schemes which is defined in pseudocode as:

p :: B -> Bool
g :: B -> A || B
h :: B -> A*
h b = Nil        ,  p b
    = a : h b'   , ¬p b
    where a, b' = g b

The scheme looks like:

p (not shown) is the predicate which "decides" what to return on current step: Nil or to continue to recursion.

It can be easy coded in Python:

def ana(b, g, p):
    if p(b): return []
    else:
        a, b_ = g(b)
        return a + ana(b_, g, p)

Most known example of usage is:

def myzip(l0, l1):
    def g(b):
        x, *xs = b[0]
        y, *ys = b[1]
        if not xs and ys: xs = [None]
        if not ys and xs: ys = [None]
        return ([(x, y)], (xs, ys))
    def p(b):
        return not (b[0] or b[1])
    return ana((l0, l1), g, p)

print(myzip([1,2,3,4], [10,20,30]))
print(list(zip([1,2,3], [10,20,30])))

A specially ZIP looks like:

what is in pseudocode:

zip :: A* || B* -> (A || B)*
zip = ANA<g, p>, where:
  g (a:as, b:bs) = ((a,b), (as, bs))
  p (as, bs) = (as=Nil) | (bs=Nil) -- until one of tails is not empty

Whether it is possible to imagine a parallel form?

Download all files by mime type

Download files of some types from URL:

wget -A ps,djvu -m -p -E -k -K -np -nH -L -l <DEEP> -e robots=off URL

all *.ps, *.djvu will be saved in own directories, but without host folder.

Intervals merge

Two simple algorithms of interval merge, which I designed yesterday while was sick :)

First (and simplest) algorithm

First, is very dumb and is based on check of edges projection: if projected edge (node) is contained in another interval then we have solid interval as result (we must merge them), elsewhere - keep original intervals, see picture:

Python implementation:

# predicat: `x` is contained in (x0, x1)
c = lambda x, x0, x1: x0 <= x <= x1

# merge-I
def m1(i1, i2):
    i1, i2 = map(isort, (i1,i2))
    sx = isort(i1 + i2)
    x1, x2 = i1; x3, x4 = i2
    if c(x1, x3, x4) or c(x3, x1, x2) or c(x2, x3, x4) or c(x4, x1, x2):
        return (sx[0], sx[-1])
    else:
        return ((sx[0], sx[1]), (sx[2], sx[3]))

where isort() is sort function, which returns tuple instead of list:

# sort interval `i`
isort = lambda i: tuple(sorted(i))

Don't forget that first is sort of intervals (normalizing) and then sort of all points - see sx.

Second algorithm

Second is more interesting. It is based on gap detection: we try to find - is there gap between intervals? If it exists then we return 2 intervals as is, otherwise - merge them into one by get (first, last) of sorted points.

where dx is difference between 2nd point of 1st interval - 1st point of 2nd interval (intervals are sorted, so "1st" and "2nd" means index in order), i.e.

D_x = I₁₂ - I₂₁

X_s = {X₁ ≼ X₂ ≼ X₃ ≼ X₄}
I_s = {I₁ ≼ I₂}

I₁₂ - I₂₁ ≥ 0 =>  RESULT := [X₁, X₄]
I₁₂ - I₂₁ < 0     RESULT := [[X₁, X₂], [X₃, X₄]]

where I is interval (pair of 2 X points).

# Tuple 0st item selector
p1 = lambda p: p[0]

# merge-II
def m2(i1, i2):
    i1, i2 = map(isort, (i1,i2))
    sx = isort(i1 + i2)
    si = sorted((i1, i2), key=p1)
    if si[0][1] - si[1][0] >= 0:
        return (sx[0], sx[-1])
    else:
        return ((sx[0], sx[1]), (sx[2], sx[3]))

Test it:

# assert
def ass(a, b):
    if a != b: raise AssertionError('%r != %r' % (a,b))

# asserts algo. m1
ass(((1,2), (10,20)), m1((1,2), (10,20)))
ass(((1,2), (10,20)), m1((2,1), (20,10)))
ass((1,20), m1((2,1), (2,20)))
ass((1,20), m1((10,1), (2,20)))
ass((1,20), m1((20,1), (5,20)))
ass((1,20), m1((20,1), (5,10)))
ass((1,20), m1((20,1), (1,10)))
ass((-1,20), m1((20,1), (-1,10)))
ass((-1,20), m1((20,1), (-1,1)))
ass(((-1,0), (1,20)), m1((20,1), (-1,0)))
ass((1,20), m1((2,10), (20,1)))

ass(((1,2), (10,20)), m2((1,2), (10,20)))
ass(((1,2), (10,20)), m2((2,1), (20,10)))
ass((1,20), m2((2,1), (2,20)))
ass((1,20), m2((10,1), (2,20)))
ass((1,20), m2((20,1), (5,20)))
ass((1,20), m2((20,1), (5,10)))
ass((1,20), m2((20,1), (1,10)))
ass((-1,20), m2((20,1), (-1,10)))
ass((-1,20), m2((20,1), (-1,1)))
ass(((-1,0), (1,20)), m2((20,1), (-1,0)))
ass((1,20), m2((2,10), (20,1)))

print 'ok.'

These algorithms are based on metrics: if we can map nodes to natural numbers, we can apply algorithms to intervals of such nodes, For example, nodes can be cities, and metric will be distance from some center, e.g. capital. This means that it's easy to merge path fragments where path nodes are cities. You can imagine any other case sutisfied such condition.