комонады и деревья

точно комонады, а то для данной задачи и http://learnyouahaskell.com/functionally-solving-problems#heathrow-to-london хватит?

Scala онанизм не поощряет. Извратиться можно, но за онанизмом пожалуйста в Haskell

реквестирую возможность забана пользователей на темы с конкретным тегом.

Что значит «сверху вниз»?

Вообще такие задачи обычно решаются имплементацией на Хаскеле и трудоемким утомительным ее портированием на нерабочий кусок гов^W^W^Wскалу

Я не очень понимаю зачем для решения конкретной задачи вообще строить дерево, т.к. ленивого списка (aka stream в scala) должно хватать, стандатное решение для таких задач это:

solve = head . filter isFinal . unfoldr go
  where
    go = go' mp

где mp - карта страны, зерно unfodr - это фронт алгоритма т.е. (координаты точки в которую ты можешь попать, суммарное расстояние до точки, история пути, список пройденых точек). На каждом шагу у тебя в списке первой стоит точка с мин расстоянием пути до неё, ты «переходишь» на неё, т.е. для всех точек в которые из неё можно дойти ты суммируешь расстояние до этой точки с расстояниями до след пунктов фильтруешь посещенные и кладёшь их в голову потока, лениво сортируя. В общем-то все.

Реализация аналогичного алгоритма на скале была в курсе на курсере, последняя задача. За полезными опимизациями и правильным подходом к решению смотреть «Жемчужины проетирования алгоритмов. Функциональный поход» глава «Делаем сотню».

Stream в скале только (тоже) нерабочий, нужно использовать EphemeralStream из scalaz

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

В Scala проблема в for, а не в самом Stream. Просто голова потока держится гораздо дольше, чем нужно, а потому память не освобождается вовремя. А for - это наиболее простой способ использовать Stream.

Вообще, по прошествии времени прихожу к выводу, что в Scala порядком накосячили в дизайне, но, тем не менее, она в хипстерском тренде сейчас.

больше я в скалу не вдавался

А зря. Вот, например, титанические потуги в языке, не поощряющем онанизм, изобразить

const :: a -> b -> a
const x _ = x

Фантастически интересная эта скала, на самом деле.

Что это за херня написана? Разъяснил бы, дружок.

Пистон знаешь? Это

def const(x,y):
  return x
# для извращенцев так
const = lambda x,y: x

там каррированая функция

каррированая

Там вообще-то в самой первой строке корректное, полностью рабочее решение:

def const[A,B](a: A) = (b: B) => a

Кстати что-то вроде этого вот:

// The identity functor that maps every type to itself
type Id[A] = A
 
// A constant functor that maps every type to A
trait Const[A] { type Apply[B] = A }
 
// A natural transformation between functors
trait ~>[F[_],G[_]] { def apply[B](f: => F[B]): G[B] }
 
// A natural transformation from the identity functor to the constant functor,
// or if you like, the type of functions that return A but are
// polymorphic in their argument.
type K[A] = Id ~> Const[A]#Apply
 
// The non-strict, universally quantified constant function.
def const = new (Id ~> K) {
  def apply[A](a: => A) = new K[A] {
    def apply[B](b: => B) = a
  }
}