[haskell] объясните механику рекурсивного определения

Не помню Haskell очень сильно, но там же типа нет, он его родить должен?

Scala онально карает если рекурсивное определение не содержит типа результата. Тип можно не писать если он очевиден. Если определение рекурсивное, то нифига это не очевидно

да не, тип есть. я его явно для ф-и f описал

явно задан тип ф-и ф.

Где тут тип?

b = f b

Весь код в студию если можна

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

type Automat2 = State -> State -> State
data State = State ((Char,Int) -> (Failable Action, State))

 
getTask2Automat :: Automat2
getTask2Automat (State noToken) (State whenCompl) = State s0
    where 
    (State s0) = (getSpacesAutomat *|* getCCommentAutomat 
                                   *|* getLineCommentAutomat *|* getParameterAutomat) (State whenCompl) (State s0)

 
getSpacesAndCommentsAutomat :: Automat2
getSpacesAndCommentsAutomat (State noToken) (State whenCompl) = (State sSnC)
    where 
        (State sSnC) = ((getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) (State sSnC))

вот так рабоатае, а так зацикливается:

getSpacesAndCommentsAutomat :: Automat2
getSpacesAndCommentsAutomat (State noToken) (State whenCompl) = sSnC
    where 
        sSnC = ((getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) (State sSnC))

p.s. и еще один вопрос. как рантайм понимает что программа зациклась? ведь программа не весить, а всего после 10-ка циклов завершается с ошибкой <<loop>>

Хм, я вас не понял, думал ошибка компиляции, сделал предположение. Так не, не эксперт

не. я долго не опнимал почему программа зацикливается. а потом для прекола сделал паттер-матчинг и оно заработало.

что меня удивило. вернее меня удивило не то что оно заработало, а то, что оно не работало без паттерн-матчинга.

Может потому, что эти строки не эквивалентны?

(State sSnC) = ((getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) (State sSnC))
        sSnC = ((getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) (State sSnC))

ошибся когда копипастил, конечно же так даже не скомпилится было так:

(State sSnC) = ((getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) (State sSnC))
        sSnC = ((getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) sSnC

Что-то я в типизацию не очень врубаюсь. Как оно у тебя компилится-то вообще? Если тип твоей getSpacesAndCommentsAutomat (боже, какое отвратительное имя) - Automat2, то во втором примере тип sSnC должен быть State, поскольку это результат функции типа Automat2, применённой к двум аргументам. Тогда выражение (State sSnC) вообще не типизируется, так как конструктор State ждёт не тип State, а тип ((Char,Int) -> (Failable Action, State)).

Если же ты описАлся, и во втором варианте должно быть

sSnC = (getCCommentAutomat *|* getLineCommentAutomat *|* getSpacesAutomat) (State whenCompl) sSnC

Давай на простом примере; пусть у нас есть

data A = A Int
f :: A -> A
f (A n) = A 1

Так вот, в этом случае минимальным решением уравнения «b = f b» будет жопа, то есть (_|_). Потому как если аргументом f окажется именно она, то паттерн-матчинг обломается, и результатом тоже будет жопа. То есть, (_|_) удовлетворяет этому уравнению - ура, всё хорошо (то есть, плохо).

А вот минимальным решением уравнения «A b = f (A b)» жопа не будет - если её туда подставить, получится «A (_|_) = f (A (_|_))»; паттерн-матчинг в этом случае пройдёт, и получится «A (_|_) = A 1», то есть "(_|_) = 1", что неверно.

Что можно сделать, чтобы это поправить. Правильный ответ - сделать функцию f поленивее. Один из способов этого добиться - написать её определение как «f _ = A 1». Если n всё-таки требуется, можно использовать ленивый паттерн: «f ~(A n) = A 1». А самое лучшее, в данном случае - использовать не «data», а «newtype»:

newtype A = A Int
f (A n) = A 1

У тебя State - почему-то «data». В данном случае «newtype» более чем показан.

Да, и: в подобных именах как минимум части «get-» и "-tomat" явно лишние. «spacesAndCommentsA» смотрится на порядок лучше.

> А самое лучшее, в данном случае - использовать не «data», а «newtype»:

спасибо. действительно помогло.

и что это за жопа такая, ссылкой поделить, а? а то я не понял, почему оно циклилось.

А самое лучшее, в данном случае - использовать не «data», а «newtype»:

спасибо. действительно помогло.

и что это за жопа такая, ссылкой поделить, а? а то я не понял, почему оно циклилось.

а ты мне говорил в прошлом топике, что здесь нью тайп нужен:

newtype и runState плюсую, а на state transformer не похоже совершенно.

а я дурак не послушал. но зато новому научусь на данной ошибке :)))))

и что это за жопа такая, ссылкой поделить, а? а то я не понял, почему оно циклилось.

Смотри. Всё, что на самом деле делает Хаскель - это решает уравнения. Причём он ищет не какое-то решение, а минимально возможное. «Минимально» - не в смысле «ноль вместо единицы». Иногда говорят «минимально определённое».

Далее, в каждом Хаскельном типе имеется такой специфический элемент, который обозначается _|_ (я предпочитаю писать его в скобках: (_|_)), а произносится по-английски «bottom», одно из возможных значений этого слова - «жопа». Он «менее определён», чем всё остальное. Для примитивных типов вроде Int все остальные значения не сравнимы: ни 0, ни 1, ни 2 не являются менее определёнными, чем другие. Поэтому для примитивных типов иерархия выглядит так:

-2 -1 0  1 2
  \ \ | / /
   \ \|/ /
    \_|_/
      |
     жопа

       (1, 2)
      /      \
(1, жопа)  (жопа, 2)
      \      /
    (жопа, жопа)
         |
        жопа

Так вот, Хаскель ищет наименьшее (наименее определённое) решение уравнения. Таковое существует, и есть алгоритм его поиска. Проблема в том, что значение (_|_), если его пытаются, например, вывести на экран, или сделать по нему паттерн-матчинг, может вызвать ошибку - а может и зациклиться. Нет способа выяснить наверняка. Если там нормальное значение, то Хаскель его найдёт; но если минимальным решением является жопа, то может получиться и цикл.

Подробнее - гугли domain theory.

Да, ещё одно. Если мы пишем

data A = A B

  ...
   |
A жопа
   |
 жопа

data A = A B | A' C

  ...        ...
   |          |
A жопа    A' жопа
      \  /
      жопа

newtype A = A B

     ...
      |
жопа = A жопа

Спасибо, очень понятно всё расписал

Тебе надо написать книжку о жоХаскеле. Действительно очень хорошо всё расписал.

Yet another monad tutorial?

Может быть. Я пока статейки в свой ЖЖ пописываю.

Если не вдаваться в domain theory, то можно объяснить немного по-другому на пальцах.

Функции бывают строгими по своему аргументу, это значит, что они при любом вызове этот аргумент вычислят. Если в твоем примере b = f b функция f строга по своему аргументу, то вычисление b уходит в бесконечный цикл, поскольку b = f b = (дальше f вычисляет b) = f (f b) = (дальше опять f вычисляет b) = f (f (f b)) = ...

В противоположность этому, если f в качестве аргумента подсунуть то, что возможно вычислить, то все станет гораздо лучше.

data A = A Int deriving Show

f :: A -> A
f (A _) = A 0

b = f b

A a = f (A a)

-- main = print b
-- output: <<loop>>

-- main = print a
-- output: 0

А, не читал внимательно, уже все есть.

>Yet another monad tutorial?

Может быть. Я пока статейки в свой ЖЖ пописываю.

не, этого добра хватает, лучше про какие-то тонкости хацкеля

з.ы. дай ссылку на ЖЖ.

http://migmit.livejournal.com

спасибо

Про жопы (никогда бы не подумал, лол) подробно написано в gentle introduction into haskell 98.pdf

чуть другой вопрос

как в хаскеле со стиранием типов?

там можно сделать функцию, которая бы (например) на каждом списке целых выдавала 2, на любом другом списке 1, на любом другом типе данных 0 ?

а чеб не заюзать для этого классы типов? хотя ф-и для определения типа есть.

там можно сделать функцию, которая бы (например) на каждом списке целых выдавала 2, на любом другом списке 1, на любом другом типе данных 0 ?

В принципе, вроде бы, делается, но, чтобы понять, как, нужно иметь хотя бы пололега в Хаскель-фу.

а чеб не заюзать для этого классы типов?

Как минимум — инстансы будут перекрываться.

можешь пояснить. где они будут перекрываться?

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

Можно. Например, так:

import Data.Typeable

func :: Typeable a => a -> Int
func x = if con == typeRepTyCon typeRepLI
         then if typeOf x == typeRepLI
              then 2
              else 1
         else 0
  where
    typeRepLI = typeOf (undefined :: [Int])
    (con, _) = splitTyConApp (typeOf x)

*Main> func ([] :: [Int])
2
*Main> func ([] :: [Char])
1
*Main> func 0
0

тоже сначала вспомнил про Typeable, но у меня появился вопрос: для всех ли типов есть инстанс класса тайпэйбл?

Для базовых типов объявлено в Data.Typeable, а для пользовательских есть deriving Typeable.

можешь пояснить. где они будут перекрываться?

«Список целых» есть частный случай «списка», который, в свою очередь, частный случай «любого типа».

для всех ли типов есть инстанс класса тайпэйбл?

Нет, не для всех.

Для базовых типов объявлено в Data.Typeable, а для пользовательских есть deriving Typeable.

Не спасёт. По крайней мере, не всегда.

{-# LANGUAGE GADTs #-}
data Delayed a where Delayed :: b -> (b -> a) -> Delayed a
force :: Delayed a -> a
force (Delayed b h) = h b -- тут всё в порядке
checktype :: Delayed a -> Int
checktype (Delayed b h) = func b -- а вот тут обломается, так как для b МОЖЕТ НЕ БЫТЬ instance Typeable

Typeable протаскивать через Delayed. Собственно, такой косяк будет у любого корректного решения с классами, иначе в динамике не узнать, каким типом является то, что вытащили из Delayed.

Typeable протаскивать через Delayed.

Это если код с Delayed писали мы.