В ширину: мы строим потенциально бесконечное дерево решений:
start : (map ... ) : (map ...) ...
где на каждом следующем шаге (рекурсивном вызове map solve) мы получаем следующие состояния и проверяем являются ли они целевыми.
В Haskell надо смотреть не на вызовы, которые ленивы, а на паттерн матчинг, который энергичен.
Подробнее.
start : map f nextStates не значит даже что nextStates вычислятся. Т.е. сначала будет проверка start == goal. Затем вычислится наличие(!) первого(!) элемента nextStates, чтобы убедиться, что хоть один элемент у нас да есть, пусть и пока не вычисленный. Поскольку вычисление рекурсивное дальше начнут проверяться == goal уже состояние из nextStates, вычисляясь по мере надобности -- а это обход следующего уровня дерева слева-направо. Т.е. это именно поиск в ширину, просто на ленивом языке он так пишется.
no subject
start : (map ... ) : (map ...) ...
где на каждом следующем шаге (рекурсивном вызове map solve) мы получаем следующие состояния и проверяем являются ли они целевыми.
В Haskell надо смотреть не на вызовы, которые ленивы, а на паттерн матчинг, который энергичен.
Подробнее.
start : map f nextStates не значит даже что nextStates вычислятся. Т.е. сначала будет проверка start == goal. Затем вычислится наличие(!) первого(!) элемента nextStates, чтобы убедиться, что хоть один элемент у нас да есть, пусть и пока не вычисленный. Поскольку вычисление рекурсивное дальше начнут проверяться == goal уже состояние из nextStates, вычисляясь по мере надобности -- а это обход следующего уровня дерева слева-направо. Т.е. это именно поиск в ширину, просто на ленивом языке он так пишется.