Как реализуется GUI на чистом функциональном языке без состояния (например, на Haskell)?
C чего вы взяли, что в Хаскеле «нет состояния»? С состоянием позволяют работать монады ST, State (трансформер StateT), и, конечно, IO. Это может работать местами менее производительно, без каких-то доп. гарантий, но это полноценная рабочая часть языка — факт. И да, ST и IO вполне можно реализовать на самом Хаскеле.

Вместо изменения значения поля в структуре создается новая структура, дублирующая все поля из старой, кроме поля, которое надо изменить.
Для любого языка имеются библиотеки, написанные на более низком уровне. Для одних языков их больше, для других — меньше.
Как делаются библиотеки под Haskell я не знаю, но Вас интересует именно аспект, связанный с сохранением чистоты при работе с GUI. На уровне использования языка, сохранить чистоту можно, оборачивая все «нечистые» вычисления в монады, например, в IO. Удобно использовать представление, которое в математике называется категорией Клейсли, когда «нечистая» функция A -> B превращается в чистую A -> IO B. Примеры привёл egorinsk комментарием выше.